LeetCode Add Two Numbers II

LeetCode Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

有两个数字链表,分别存储了两个整数,要求把这两个整数加起来。和LeetCode Add Two Numbers的区别是,之前的链表最低位在表头,我们正常加法也是从低位到高位,所以之前的题可以直接从表头开始加。但是这个题稍有不同,最低位在表尾,表头是最高位,所以必须先跑到链表尾才能做加法。一种方法是我们可以先把链表逆序,这样就可以用之前的解法了,但是题目中说不能修改原链表,所以不能用这种解法。

那么怎样获取到表尾的数据进行加法呢,我们可以把两个链表压入两个堆栈,因为堆栈是后进先出,所以再次从栈顶取数据做加法的时候就是从低位到高位的加了。

完整代码如下:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		stack<int> s1, s2;
		while (l1) {
			s1.push(l1->val);
			l1 = l1->next;
		}
		while (l2) {
			s2.push(l2->val);
			l2 = l2->next;
		}
		ListNode* ans = new ListNode(1); // 预设好的最高位进位:-)
		int sum = 0;
		while (!s1.empty() || !s2.empty()) {
			if (!s1.empty()) {
				sum += s1.top();
				s1.pop();
			}
			if (!s2.empty()) {
				sum += s2.top();
				s2.pop();
			}
			ListNode* tmp = new ListNode(sum%10);
			tmp->next = ans->next;
			ans->next = tmp;
			sum /= 10; // 下一次的进位
		}
		if (sum)return ans;
		else return ans->next;
	}
};

本代码提交AC,用时55MS。

代码中有两个地方解释一下,一般链表的题都会在结果链表中加一个没用的头结点,一般是0,但是因为最终的加法结果可能进位,所以把表头的值定为1,如果有进位,这个1也可以用上,如果没进位,就返回1的next。另一个就是我们没有单独定义add1、add2和carry,而是只用一个sum变量搞定了,sum%10相当于进位之后的结果,sum/10相当于进位。

Leave a Reply

Your email address will not be published. Required fields are marked *