P002-Add-Two-Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

思路分析

就是两个链表的并行遍历，并不怎么难。

  • 肯定得遍历两个链表
  • 两链表长度相同时，对应位置相加并将进位保留到下一次循环
  • 两链表长度不相同时，往长度较短的链表尾部补零(最高位和现实生活中的数字恰好相反)

代码

java

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
/***
 * 2 4 3        2 4 3 0     1 2 3 4 0
 * 5 6 4        5 6 4 9     6 7 8 9 9
 * -------      -------     ----------
 * 7 0 8        7 0 8 9     7 9 1 4 0 1
 * 
 * **/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null)
        return l2;
    if (l2 == null)
        return l1;
    ListNode l = l1;
    ListNode r = l2;
    ListNode ret = new ListNode(0);
    int up = 0;
    int currentVal = 0;
    ListNode last = ret;
    while (l != null || r != null) {
        // 两个链表长度不一致：补零
        if (l == null)
            l = new ListNode(0);
        if (r == null)
            r = new ListNode(0);
        // 当前值:加上进位
        currentVal = (l.val + r.val) + up;
        if (currentVal >= 10) {
            up = currentVal / 10;// 为下一轮提供的进位
            currentVal = currentVal % 10;// 当前值
        } else {
            up = 0;
        }
        // 新节点
        ListNode newNode = new ListNode(currentVal);
        last.next = newNode;
        last = last.next;
        l = l.next;
        r = r.next;
    }
    if (up != 0) {
        last.next = new ListNode(up);
    }
    return ret.next;
}

python

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
def addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    if (not l1) : return l2
    if (not l2) : return l1
    l = l1;r = l2;
    ret = ListNode(0);last = ret
    up = 0;currentVal = 0
    
    while (l or r):
        if not l:l = ListNode(0)
        if not r:r = ListNode(0)
        
        currentVal = (l.val + r.val) + up
        
        if currentVal >= 10:
            up = currentVal / 10
            currentVal = currentVal % 10
        else:
            up = 0
        
        newNode = ListNode(currentVal)
        last.next = newNode
        last = last.next
        
        l = l.next
        r = r.next
    
    # end while
    
    if up != 0:
        last.next = ListNode(up)
    
    return ret.next