[Leetcode] Add Two Numbers 連結清單數相加

Add Two Numbers

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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

遞歸寫法 Recursive

複雜度

時間O(n) 空間(n) 遞歸棧空間

思路

本題的思路很簡單，按照國小數學中學習的加法原理從末尾到首位，對每一位對齊相加即可。技巧在于如何處理不同長度的數字，以及進位和最高位的判斷。這裡對于不同長度的數字，我們通過将較短的數字補0來保證每一位都能相加。遞歸寫法的思路比較直接，即判斷該輪遞歸中兩個ListNode是否為null。

• 全部為null時，傳回進位值
• 有一個為null時，傳回不為null的那個ListNode和進位相加的值
• 都不為null時，傳回 兩個ListNode和進位相加的值

代碼

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1,l2,0);
    }
    
    public ListNode helper(ListNode l1, ListNode l2, int carry){
        if(l1==null && l2==null){
            return carry == 0? null : new ListNode(carry);
        }
        if(l1==null && l2!=null){
            l1 = new ListNode(0);
        }
        if(l2==null && l1!=null){
            l2 = new ListNode(0);
        }
        int sum = l1.val + l2.val + carry;
        ListNode curr = new ListNode(sum % 10);
        curr.next = helper(l1.next, l2.next, sum / 10);
        return curr;
    }
}           

疊代寫法 Iterative

複雜度

時間O(n) 空間(1)

思路

疊代寫法相比之下更為晦澀，因為需要處理的分支較多，邊界條件的組合比較複雜。過程同樣是對齊相加，不足位補0。疊代終止條件是兩個ListNode都為null。

注意

• 疊代方法操作連結清單的時候要記得手動更新連結清單的指針到next
• 疊代方法操作連結清單時可以使用一個dummy的頭指針簡化操作
• 不可以在其中一個連結清單結束後直接将另一個連結清單串接至結果中，因為可能産生連鎖進位

代碼

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        if(l1 == null && l2 == null){
            return dummyHead;
        }
        int sum = 0, carry = 0;
        ListNode curr = dummyHead;
        while(l1!=null || l2!=null){
            int num1 = l1 == null? 0 : l1.val;
            int num2 = l2 == null? 0 : l2.val;
            sum = num1 + num2 + carry;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            carry = sum / 10;
            l1 = l1 == null? null : l1.next;
            l2 = l2 == null? null : l2.next;
        }
        if(carry!=0){
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}           

2018/2

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode((l1.val + l2.val) % 10)
        current = head
        carry = (l1.val + l2.val) // 10
        while l1.next is not None or l2.next is not None:
            num1 = 0
            num2 = 0
            if l1.next is not None:
                l1 = l1.next
                num1 = l1.val
            if l2.next is not None:
                l2 = l2.next
                num2 = l2.val
            current.next = ListNode((num1 + num2 + carry) % 10)
            carry = (num1 + num2 + carry) // 10
            current = current.next
        if carry != 0:
            current.next = ListNode(carry)
        return head           

2018/10

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{0, nil}
    curr := dummy
    carry := 0
    for l1 != nil && l2 != nil {
        val := carry
        if l1 != nil {
            val += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            val += l2.Val
            l2 = l2.Next
        }
        curr.Next = &ListNode{val % 10, nil}
        carry = val / 10
        curr = curr.Next
    }
    if carry != 0 {
        curr.Next = &ListNode{carry, nil}
    }
    return dummy.Next
}           

後續 Follow Up

Q：如果将數字從連結清單改為由數組表示的話如何解決？

A：疊代寫法仍然可以用于數組，具體請參見大整數相加的專題文章。

Q：如果這是一個類的話該如何實作？

A：将連結清單或者數組作為成員變量(member variable)，提供對其操作的各種方法(method)。