<!-- raw HTML block --> <div><p>You are given two <strong>non-empty</strong> linked lists representing two non-negative integers. The digits are stored in <strong>reverse order</strong>, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.</p>
<p>You may assume the two numbers do not contain any leading zero, except the number 0 itself.</p>
<p> </p> <p><strong>Example 1:</strong></p> <img alt="" src="https://assets.leetcode.com/uploads/2020/10/02/addtwonumber1.jpg" style="width: 483px; height: 342px;"> <pre><strong>Input:</strong> l1 = [2,4,3], l2 = [5,6,4] <strong>Output:</strong> [7,0,8] <strong>Explanation:</strong> 342 + 465 = 807. </pre>
<p><strong>Example 2:</strong></p>
<pre><strong>Input:</strong> l1 = [0], l2 = [0] <strong>Output:</strong> [0] </pre>
<p><strong>Example 3:</strong></p>
<pre><strong>Input:</strong> l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] <strong>Output:</strong> [8,9,9,9,0,0,0,1] </pre>
<p> </p> <p><strong>Constraints:</strong></p>
<ul> <li>The number of nodes in each linked list is in the range <code>[1, 100]</code>.</li> <li><code>0 <= Node.val <= 9</code></li> <li>It is guaranteed that the list represents a number that does not have leading zeros.</li> </ul> </div>
题目大意：
数位链表(从最低位到最高位)相加
算法思路：
类似于merge sort
注意事项：
- 其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
- 所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
fake_head = ListNode(0)
carry = 0
it, it2, it_res = l1, l2, fake_head
while it or it2:
value = carry
if it:
value += it.val
it = it.next
if it2:
value += it2.val
it2 = it2.next
carry = 1 if value >= 10 else 0
value %= 10
it_res.next = ListNode(value)
it_res = it_res.next
if carry == 1:
it_res.next = ListNode(1)
return fake_head.next
算法分析：
时间复杂度为O(n + m)，空间复杂度O(1)
