AddLists

发表于 | 分类于

AddLists(将两个链表相加)

题目描述：

两个链表中保存中一系列整数，分别代表着两个整数；例如1->2->3；给定两个链表的头结点，返回两个链表中数相加后的结果。

例子：

例如给定1->2->3和2->4->5;则返回头结点，其指向的链表内容为3->6->8。

解题思路：

解题思路为：因为数据的相加需要从尾部开始，所以第一个想法是利用栈结构。将数据分别导入到两个栈中，不断的从栈顶提取出数据，相加后新建一个节点，用相加的初始值初始化该节点，并记录是否进位；下一次的相加后的新建的节点指向上一个节点即可。另外也可以将结果导入到一个新栈中，在全部计算完成之后，从栈顶取元素初始化即可。

代码如下：

其中关于链表类的定义如下：

1
2
3
4
5
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {};
};

解法一：利用三个栈来实现，需要注意的是进位的保存和计算完成之后需要判断进位来决定头结点是否为1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "ListNode.h"
#include "reverseList.h"
#include <stack>
using namespace std;
class addLists1{
public:
    ListNode* addLists(ListNode* head1, ListNode* head2) {
        stack<int> stk1;
        stack<int> stk2;
        stack<int> stk3;
        int n1 = 0;
        int n2 = 0;
        int ca = 0;
        while (head1 != NULL) {
            stk1.push(head1->val);
            head1 = head1->next;
        }                      //第一链表数据进栈
        while (head2 != NULL) {
            stk2.push(head2->val);
            head2 = head2->next;
        }                     //第二个链表数据进栈
        while (!stk1.empty() || !stk2.empty()) {
            n1 = stk1.empty() ? 0 : stk1.top();
            stk1.pop();
            n2 = stk2.empty() ? 0 : stk2.top();
            stk2.pop();
            stk3.push((n1 + n2 + ca) % 10);
            ca = ((n1 + n2 + ca) >= 10) ? 1 : 0;
        }                    //相加结果进栈保存
        ListNode* pre = new ListNode(-1);
        ListNode* cur = pre;
        while (!stk3.empty()) {
            cur->next = new ListNode(stk3.top());
            stk3.pop();
            cur = cur->next;
        }                   //将栈中元素初始化并连接
        if (ca == 1){
            pre->val = 1;
            return pre;
        }                   //最后判断最高位是否存在进位
        else
            return pre->next;
    }
};

解法二：直接将链表逆序后计算和的值并连接链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class addLists2{
public:
    ListNode* addLists(ListNode* head1, ListNode* head2){
        reverseList1 re;
        head1 = re.reverseList(head1);
        head2 = re.reverseList(head2);//链表的逆序处理
        int n1 = 0;
        int n2 = 0;
        int ca = 0;
        ListNode* cur = new ListNode(-1);
        ListNode* backup = cur;
        while(head1 != NULL || head2 != NULL){
            n1 = (head1 == NULL) ? 0 : head1->val;
            n2 = (head2 == NULL) ? 0 : head2->val;
            cur->next = new ListNode((n1 + n2 + ca) % 10);
            ca = (n1 + n2 + ca>= 10) ? 1 : 0;
            cur = cur->next;         //从头开始相加并记录进位
            head1 = (head1 == NULL) ? NULL : head1->next;
            head2 = (head2 == NULL) ? NULL : head2->next;
        }                           
        if (ca == 1){
            cur->next = new ListNode(1);
        }                           //判断最高位的进位
        cur = backup->next;
        backup->next = NULL;
        cur = re.reverseList(cur); //将结果逆序后返回
        return cur;
    }
};