445. 两数相加 II

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 404 阅读时长 ≈ 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
class Solution {
	public:
		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
			stack<int> list1, list2;
			while (l1 != nullptr) {
				list1.push(l1->val);
				l1 = l1->next;
			}
			while (l2 != nullptr) {
				list2.push(l2->val);
				l2 = l2->next;
			}
			int carry = 0;
			ListNode *dummyHead = new ListNode(-1);
			while (!list1.empty() || !list2.empty() || carry) {
				carry += !list1.empty() ? list1.top() : 0;
				carry += !list2.empty() ? list2.top() : 0;
				if (!list1.empty()) list1.pop();
				if (!list2.empty()) list2.pop();
				ListNode *node = new ListNode(carry % 10, dummyHead->next);
				dummyHead->next = node;
				carry /= 10;
			}
			return dummyHead->next;
		}
};

思路

按照算术逻辑，运算应该从低位到高位，同时用一个变量carry记录进位

那么新节点的值就等于(对应位之和+上一次运算的carry)取余10，进位carry的值就等于(对应位之和+上一次运算的carry)除以10

故而正常思维，两个链表先反转并作运算，新的节点以头插的方式连接，这样就保证了逆序

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
class Solution {
private:
	ListNode* reverseFunc(ListNode* head) {
        //头插法反转链表
		ListNode *dummyHead = new ListNode(-1, head), *tail = head;
		while (tail->next != nullptr) {
			ListNode *node = tail->next;
			tail->next = node->next;
			node->next = dummyHead->next;
			dummyHead->next = node;
		}
		return dummyHead->next;
	}
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode *dummyHead = new ListNode(-1);
		l1 = reverseFunc(l1);
		l2 = reverseFunc(l2);
		int carry = 0;
		while (l1 != nullptr || l2 != nullptr || carry) {
			carry += l1 != nullptr ? l1->val : 0;
			carry += l2 != nullptr ? l2->val : 0;
            //头插法新建链表即逆序
			ListNode *node = new ListNode(carry % 10, dummyHead->next);
			dummyHead->next = node;
			carry /= 10;
			l1 = l1 != nullptr ? l1->next : nullptr;
			l2 = l2 != nullptr ? l2->next : nullptr;
		}
		return dummyHead->next;
	}
};

但是题目竟然要求不反转链表？那就只能用栈了，代码如题解所示

两个链表的值先入栈，保证低位对低位；每次对应位出栈做运算，新的节点同样以头插的方式连接保证逆序