[C#][LeetCode] 2. Add Two Numbers

輸入兩個 ListNode 物件並將兩個相同層數的數值加總,其值若超過 10 需進位到下個節點,這題我覺得迴圈解法比遞迴更讓人腦袋卡住,可能是我功力不夠吧。

我的遞迴解答:

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

public ListNode Add(ListNode l1, ListNode l2, int addNum = 0)
{
if(l1 == null && l2 == null)
{
return null;
}

l1 = l1 ?? new ListNode(0);
l2 = l2 ?? new ListNode(0);

int i = (l1.val + l2.val) + addNum;
ListNode totalNode = new ListNode(i % 10);
if(l1.next != null || l2.next != null)
{
totalNode.next = Add(l1.next, l2.next, (i / 10));
}

if(i >= 10 && totalNode.next == null)
{
totalNode.next = new ListNode(1);
}

return totalNode;
}
}

我的迴圈作法:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {

int sumValue = 0;
int carryValue = 0;

ListNode ansNode = new ListNode(-1);

// 將 ansNode 的記憶體位置指向給 node
ListNode node = ansNode;

while(l1 != null || l2 != null)
{
sumValue = carryValue;

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

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

carryValue = (sumValue / 10);
if(carryValue > 0)
{
sumValue = (sumValue % 10);

// 若大於 10 且 l1 與 l2 都沒有下個節點,那就自己創造一個
if(l1 == null && l2 == null)
{
l1 = new ListNode(0);
}
}

if(ansNode.val == -1)
{
ansNode.val = sumValue;
}
else
{
node.next = new ListNode(sumValue);

// 將當前物件 node.next 的記憶體位置指向到 node,這樣就可以達到一層一層改變 ansNode.next 值的效果
node = node.next;
}
}

return ansNode;
}


}