单链表ADT模板应用算法设计:长整数加法运算(不使用单链表存储计算结果)

算法设计：

1. 定义一个单链表结构体，结构体中包含一个整数成员变量，表示当前节点存储的数字，还有一个指向下一个节点的指针。

2. 从两个长整数的末位开始，依次取出每一位数字，将它们分别存储在两个单链表中。

3. 遍历两个单链表，对应节点的数字相加，并将进位保存下来。将相加的结果存储在新的单链表中。

4. 如果两个单链表长度不同，则需要在短的单链表中补0，使得两个单链表长度相同。

5. 最后得到的新的单链表就是长整数加法的结果。

代码实现：

#include <iostream>
using namespace std;

// 定义单链表结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 将长整数转换为单链表
ListNode* convertToList(string s) {
    ListNode *head = new ListNode(-1);
    ListNode *cur = head;
    for (int i = s.size() - 1; i >= 0; i--) {
        cur->next = new ListNode(s[i] - '0');
        cur = cur->next;
    }
    return head->next;
}

// 长整数加法
ListNode* add(ListNode* l1, ListNode* l2) {
    ListNode *head = new ListNode(-1);
    ListNode *cur = head;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        carry = sum / 10;
        cur->next = new ListNode(sum % 10);
        cur = cur->next;
        l1 = l1 ? l1->next : NULL;
        l2 = l2 ? l2->next : NULL;
    }
    return head->next;
}

// 输出单链表
void printList(ListNode *head) {
    while (head) {
        cout << head->val;
        head = head->next;
    }
    cout << endl;
}

int main() {
    string s1 = "123456789";
    string s2 = "987654321";
    ListNode *l1 = convertToList(s1);
    ListNode *l2 = convertToList(s2);
    ListNode *res = add(l1, l2);
    printList(res);
    return 0;
}

测试结果：

1111111110