LeetCode2——两数相加

问题描述

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

示例

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

解题思路:

构造一个新的链表用于表示两束相加的和,设置新链表的根节点和游标节点,根节点用于返回最后的链表,游标节点用于跟踪计算的位置。依次取两个链表的节点的值相加,相加的和对10取余,余数作为该位节点的值,进位传到后面对应节点进行相加。然后两个链表节点后移,新链表游标后移。过程中,注意相加的结束条件,两个链表都没有节点且无进位,相加才结束。

代码展示

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
class Solution {

public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode cursor, root = new ListNode(0);
cursor = root;
while(l1 != null || l2 != null || carry != 0){
if(l1 != null){
carry += l1.val;
l1 = l1.next;
}

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

cursor.next = new ListNode(carry%10);
carry /= 10;
cursor = cursor.next;
}
return root.next;
}
}

Go版:

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
package leetcode

//ListNode is:
//Definition for singly-linked list.
//type ListNode struct {
// Val int
// Next *ListNode
//}
type ListNode struct {
Val int
Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
carry := 0
p := &ListNode{Val: 0}
dummy := &ListNode{Val: 0}
p = dummy

for {
if l1 == nil && l2 == nil && carry == 0 {
break
}

if l1 != nil {
carry += l1.Val
l1 = l1.Next
}

if l2 != nil {
carry += l2.Val
l2 = l2.Next
}

p.Next = &ListNode{Val: carry % 10}
carry /= 10
p = p.Next
}
return dummy.Next
}