By Long Luo
Leetcode 2. 两数相加 题解。
方法一:模拟链表操作
思路与算法:
最开始我的思路是将 2 个数字都读出来,然后相加,再逆向写入回去,但是发现链表数字太长,这个方法不可行。
由于两个链表长度不一致,还需要考虑不同位数对齐的问题,但是由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。
那么只需要同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为 n1 ,n2,进位值为 carry,则它们的和为 n1+n2+carry。
其中,答案链表处相应位置的数字为 (n1+n2+carry)mod10,而新的进位值为 sum−10。
需要注意的是:如果链表遍历结束后,有 carry>0 ,还需要在答案链表的后面附加一个节点,节点的值为 carry。
于是就有了那么的第一版代码:
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 46 47 48 49 50 51 52 53 54 55
| public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode pNode1 = l1; ListNode pNode2 = l2; ListNode dummyNode = new ListNode(-1); ListNode pNode = dummyNode; int carry = 0; while (pNode1 != null && pNode2 != null) { int sum = pNode1.val + pNode2.val + carry; carry = 0; if (sum >= 10) { sum -= 10; carry = 1; } ListNode node = new ListNode(sum); pNode.next = node; pNode = pNode.next;
pNode1 = pNode1.next; pNode2 = pNode2.next; }
while (pNode1 != null) { int sum = pNode1.val + carry; carry = 0; if (sum >= 10) { sum -= 10; carry = 1; } ListNode node = new ListNode(sum); pNode.next = node; pNode = pNode.next;
pNode1 = pNode1.next; }
while (pNode2 != null) { int sum = pNode2.val + carry; carry = 0; if (sum >= 10) { sum -= 10; carry = 1; } ListNode node = new ListNode(sum); pNode.next = node; pNode = pNode.next; pNode2 = pNode2.next; }
if (carry > 0) { ListNode node = new ListNode(carry); pNode.next = node; }
return dummyNode.next; }
|
实际上,上述代码可以优化,去掉多余的变量。如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 0,得到了下面的优化代码:
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
| public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyNode = new ListNode(-1); ListNode pNode = dummyNode; int carry = 0; while (l1 != null || l2 != null) { int num1 = l1 != null ? l1.val : 0; int num2 = l2 != null ? l2.val : 0; int sum = num1 + num2 + carry; carry = sum / 10; pNode.next = new ListNode(sum % 10); pNode = pNode.next;
if (l1 != null) { l1 = l1.next; }
if (l2 != null) { l2 = l2.next; } }
if (carry > 0) { pNode.next = new ListNode(carry); }
return dummyNode.next; }
|
复杂度分析
- 时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1) 的时间。
- 空间复杂度:O(1)。
方法二:递归
递归更精妙,但也更难懂!
首先,需要确定终止条件,显然当 l1 或者 l2 为空指针时,递归终止;
其次,l1 和 l2 不为空时,结果为两者之和加上进位然后mod10;
递归需要考虑进位,所以需要新写一个辅助函数,进位作为参数传递,这点比较难以想到。
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
| public static ListNode addTwoNumbers_rec(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; }
return addNode(l1, l2, 0); }
public static ListNode addNode(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null && carry == 0) { return null; }
if (l1 != null) { carry += l1.val; l1 = l1.next; }
if (l2 != null) { carry += l2.val; l2 = l2.next; }
ListNode addNode = new ListNode(carry % 10); carry = carry / 10; addNode.next = addNode(l1, l2, carry); return addNode; }
|
复杂度分析
- 时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1) 的时间。
- 空间复杂度:O(max(m,n))。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗