力扣-2-链表中两数倒序相加

评论

题目：
2. Add Two Numbers(medium)

题目大意：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路：
两个存储数字的链表中，高位在右，低位在左，正符合相加后进位的高位在右边添加的正常顺序，所以新建链表时需要使用尾插法，而不是常见的头插法，因为后者会颠倒正常的存储顺序。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Java:
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
    ListNode newHead = new ListNode(0);
    ListNode p = l1, q = l2,cur = newHead;
    int carry = 0;
    while(p != null || q != null || carry != 0){
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = x + y + carry;
        carry = sum / 10;

        //低位在前，高位在后，所以这里使用尾插法可以保证正确的顺序
        cur.next = new ListNode(sum%10);
        cur = cur.next;
        if(p != null) p = p.next;
        if(q != null) q = q.next;
    }
    return newHead.next;
}

Python:

InstantCWeedStudent

个人简介。