2. 两数相加

Posted on | In
Words count in article: 588 | Reading time ≈ 2

题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例

示例1：

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

示例2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解法

解法一：

模拟竖式加法

竖式加法就是从最低位一位一位往最高位加，如果有进位的话，再加上这个进位。此处模拟这个过程即可。不过需要注意的，两个列表未必是长度相同的。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode tmp = null;
	    ListNode result = null;

	    int carry = 0;
	    while (l1 != null || l2 != null || carry != 0) {
	        int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
	        carry = sum / 10;

	        ListNode node = new ListNode(sum % 10);
	        if (tmp == null) {
	            tmp = node;
	            result = tmp;
	        } else {
	            tmp.next = node;
	            tmp = tmp.next;
	        }

	        l1 = l1 == null ? null : l1.next;
	        l2 = l2 == null ? null : l2.next;
	    }

	    return result;
	}
}

扩展

如果，保存的位顺序是反的呢？

比如： 342+465=807

(3→4→2)+(4→6→5)=8→0→7

解法一：

按照顺序每位相加。完成之后，用两个指针（一个保存头指针p1，一个保存头指针后一个p2），从头开始遍历列表，判断p2是否大于等于10，是的话，p1对应的值，加一。然后顺移一位，直到最后。

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
public ListNode addTwoNumbersReverse(ListNode l1, ListNode l2) {
		ListNode result = new ListNode(0);
		while (null != l1 || null != l2) {
			ListNode node = new ListNode(0);
			if (null == l1) {
				node.val = l2.val;
			} else if (null == l2) {
				node.val = l1.val;
			} else {
				node.val = l1.val + l2.val;
			}

			if (null != l1) {
				l1 = l1.next;
			}

			if (null != l2) {
				l2 = l2.next;
			}

			ListNode p1 = result;
			ListNode p2 = result.next;
			while (null != p2) {
				if (p2.val >= 10) {
					p1.val += 1;
					p2.val -= 10;
				}
				p1 = p2;
				p2 = p2.next;
			}

			if (result.val == 0) {
				result = result.next;
			}
		}
		return result;
	}
0%