JJ's Blog

1. 題目（Problem Statement）

英文：

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.
中文：

給定兩個代表非負整數的非空連結串列。數字以相反的順序存儲，每個節點包含一個數字。將這兩個數相加並將和作為一個連結串列返回。

你可以假設這兩個數字不包含任何前導零，除非數字本身是0。

2. 題目說明與解決方案（Explanation and Solution）

這是一個常見的鏈表問題，需要模擬加法的過程。我們從鏈表的頭部開始，將相應位置的數字相加，並記錄進位。最終，我們得到了一個新的鏈表，代表兩數之和。

3. 範例（Example）

1Input:
2  L1: 2 -> 4 -> 3
3  L2: 5 -> 6 -> 4
4Output:
5  Result: 7 -> 0 -> 8

4. 限制條件（Constraints）

節點數介於 1 到 100 之間。
每個節點包含一個數字，範圍是 0 到 9。
這兩個鏈表表示的數字是非負整數。

5. C# 解法（C# Solution）

 1namespace UnitTestDay2_AddTwoNumbers
 2{
 3    public class Solution
 4    {
 5        public class ListNode
 6        {
 7            public int val;
 8            public ListNode next;
 9            public ListNode( int val = 0, ListNode next = null )
10            {
11                this.val = val;
12                this.next = next;
13            }
14        }
15
16        public ListNode AddTwoNumbers( ListNode l1, ListNode l2 )
17        {
18            ListNode dummyHead = new ListNode( 0 );
19            ListNode current = dummyHead;
20            int carry = 0;
21
22            while (l1 != null || l2 != null)
23            {
24                int x = l1?.val ?? 0;
25                int y = l2?.val ?? 0;
26                int sum = carry + x + y;
27
28                carry = sum / 10;
29                current.next = new ListNode( sum % 10 );
30
31                l1 = l1?.next;
32                l2 = l2?.next;
33                current = current.next;
34            }
35
36            if (carry > 0)
37            {
38                current.next = new ListNode( carry );
39            }
40
41            return dummyHead.next;
42        }
43    }
44}

6. C# 程式碼說明（C# Code Explanation）

這是 C# 的解法，我們使用了 ListNode 類別來表示連結串列中的節點。主要邏輯在 AddTwoNumbers 方法中。

我們建立一個 dummyHead 作為結果連結串列的虛擬頭節點，方便操作。
使用 current 指針來表示當前節點，初始指向 dummyHead。
carry 變數用來處理進位，初始值為 0。
我們使用 while 迴圈遍歷兩個輸入的連結串列 l1 和 l2，並同時進行加法操作和進位處理。
在每一輪迴圈中，我們取出 l1 和 l2 的值（如果存在），加上上一輪的進位值 carry，計算總和 sum 和進位。
將 sum % 10 放入結果串列的當前節點中，同時將進位 carry 更新為 sum / 10。
移動 l1、l2 和 current 指針以繼續下一輪計算。
最後，如果還有剩餘的進位，我們在結果連結串列的尾部添加一個新節點。
最終，我們返回 dummyHead 的下一個節點，即最終的結果連結串列。

7. C# 單元測試（C# Unit Tests）

 1namespace UnitTestDay2_AddTwoNumbers.Tests
 2{
 3    [TestClass()]
 4    public class SolutionTests
 5    {
 6        private Solution UT = new Solution();
 7
 8        [TestMethod()]
 9        public void Test1()
10        {
11            // Arrange
12            ListNode l1 = CreateLinkedList( 2, 4, 3 );
13            ListNode l2 = CreateLinkedList( 5, 6, 4 );
14            ListNode expected = CreateLinkedList( 7, 0, 8 );
15
16            // Act
17            ListNode result = UT.AddTwoNumbers( l1, l2 );
18
19            // Assert
20            Assert.IsTrue( CompareLinkedLists( expected, result ) );
21        }
22
23        [TestMethod()]
24        public void Test2()
25        {
26            // Arrange
27            ListNode l1 = CreateLinkedList( 0 );
28            ListNode l2 = CreateLinkedList( 0 );
29            ListNode expected = CreateLinkedList( 0 );
30
31            // Act
32            ListNode result = UT.AddTwoNumbers( l1, l2 );
33
34            // Assert
35            Assert.IsTrue( CompareLinkedLists( expected, result ) );
36        }
37
38        [TestMethod()]
39        public void Test3()
40        {
41            // Arrange
42            ListNode l1 = CreateLinkedList( 9, 9, 9, 9, 9, 9, 9 );
43            ListNode l2 = CreateLinkedList( 9, 9, 9, 9 );
44            ListNode expected = CreateLinkedList( 8, 9, 9, 9, 0, 0, 0, 1 );
45
46            // Act
47            ListNode result = UT.AddTwoNumbers( l1, l2 );
48
49            // Assert
50            Assert.IsTrue( CompareLinkedLists( expected, result ) );
51        }
52
53        // Helper method to create a linked list from an array of values
54        private ListNode CreateLinkedList( params int[] values )
55        {
56            if (values == null || values.Length == 0)
57                return null;
58
59            ListNode head = new ListNode( values[0] );
60            ListNode current = head;
61
62            for (int i = 1; i < values.Length; i++)
63            {
64                current.next = new ListNode( values[i] );
65                current = current.next;
66            }
67
68            return head;
69        }
70
71        // Helper function to compare two linked lists
72        private bool CompareLinkedLists( ListNode list1, ListNode list2 )
73        {
74            while (list1 != null && list2 != null)
75            {
76                if (list1.val != list2.val)
77                {
78                    return false;
79                }
80                list1 = list1.next;
81                list2 = list2.next;
82            }
83
84            // Check if both lists are of equal length
85            return list1 == null && list2 == null;
86        }
87    }
88}

8. Python 解法（Python Solution）

 1class ListNode:
 2    def __init__(self, val=0, next=None):
 3        self.val = val
 4        self.next = next
 5
 6class Solution:
 7    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
 8        dummy_head = ListNode(0)
 9        current = dummy_head
10        carry = 0
11
12        while l1 or l2:
13            x = l1.val if l1 else 0
14            y = l2.val if l2 else 0
15            _sum = carry + x + y
16
17            carry = _sum // 10
18            current.next = ListNode(_sum % 10)
19
20            if l1:
21                l1 = l1.next
22            if l2:
23                l2 = l2.next
24            current = current.next
25
26        if carry > 0:
27            current.next = ListNode(carry)
28
29        return dummy_head.next

9. Python 程式碼說明（Python Code Explanation）

這是 Python 的解法，和 C# 解法類似。我們使用了 ListNode 類別來表示連結串列中的節點，並實現了 addTwoNumbers 方法來執行加法操作和進位處理。

我們建立一個 dummy_head 作為結果連結串列的虛擬頭節點。
使用 current 指針來表示當前節點，初始指向 dummy_head。
carry 變數用來處理進位，初始值為 0。
我們使用 while 迴圈遍歷兩個輸入的連結串列 l1 和 l2，同時進行加法操作和進位處理。
在每一輪迴圈中，我們取出 l1 和 l2 的值（如果存在），加上上一輪的進位值 carry，計算總和 _sum 和進位。
將 _sum % 10 放入結果串列的當前節點中，同時將進位 carry 更新為 _sum // 10。
移動 l1、l2 和 current 指針以繼續下一輪計算。
最後，如果還有剩餘的進位，我們在結果連結串列的尾部添加一個新節點。
最終，我們返回 dummy_head 的下一個節點，即最終的結果連結串列。

10. Python 單元測試（Python Unit Tests）

 1namespace UnitTestDay2_AddTwoNumbers.Tests
 2{
 3    [TestClass()]
 4    public class SolutionTests
 5    {
 6        private Solution UT = new Solution();
 7
 8        [TestMethod()]
 9        public void Test1()
10        {
11            // Arrange
12            ListNode l1 = CreateLinkedList( 2, 4, 3 );
13            ListNode l2 = CreateLinkedList( 5, 6, 4 );
14            ListNode expected = CreateLinkedList( 7, 0, 8 );
15
16            // Act
17            ListNode result = UT.AddTwoNumbers( l1, l2 );
18
19            // Assert
20            Assert.IsTrue( CompareLinkedLists( expected, result ) );
21        }
22
23        [TestMethod()]
24        public void Test2()
25        {
26            // Arrange
27            ListNode l1 = CreateLinkedList( 0 );
28            ListNode l2 = CreateLinkedList( 0 );
29            ListNode expected = CreateLinkedList( 0 );
30
31            // Act
32            ListNode result = UT.AddTwoNumbers( l1, l2 );
33
34            // Assert
35            Assert.IsTrue( CompareLinkedLists( expected, result ) );
36        }
37
38        [TestMethod()]
39        public void Test3()
40        {
41            // Arrange
42            ListNode l1 = CreateLinkedList( 9, 9, 9, 9, 9, 9, 9 );
43            ListNode l2 = CreateLinkedList( 9, 9, 9, 9 );
44            ListNode expected = CreateLinkedList( 8, 9, 9, 9, 0, 0, 0, 1 );
45
46            // Act
47            ListNode result = UT.AddTwoNumbers( l1, l2 );
48
49            // Assert
50            Assert.IsTrue( CompareLinkedLists( expected, result ) );
51        }
52
53        // Helper method to create a linked list from an array of values
54        private ListNode CreateLinkedList( params int[] values )
55        {
56            if (values == null || values.Length == 0)
57                return null;
58
59            ListNode head = new ListNode( values[0] );
60            ListNode current = head;
61
62            for (int i = 1; i < values.Length; i++)
63            {
64                current.next = new ListNode( values[i] );
65                current = current.next;
66            }
67
68            return head;
69        }
70
71        // Helper function to compare two linked lists
72        private bool CompareLinkedLists( ListNode list1, ListNode list2 )
73        {
74            while (list1 != null && list2 != null)
75            {
76                if (list1.val != list2.val)
77                {
78                    return false;
79                }
80                list1 = list1.next;
81                list2 = list2.next;
82            }
83
84            // Check if both lists are of equal length
85            return list1 == null && list2 == null;
86        }
87    }
88}

11. 總結（Summary）

這個題目的目的是將兩個以連結串列表示的數相加，並返回結果。總結一下解題技巧，解決這個問題的關鍵在於有效處理進位，並且在兩個連結串列不等長的情況下進行迭代計算，模擬加法的過程。時間複雜度為O(max(N, M))，其中N和M分別是兩個鏈表的長度，空間複雜度為O(max(N, M))，主要是結果鏈表的空間。

LeetCode #2 Add Two Numbers