[Leetcode] Add Two Numbers 鏈表數(shù)相加

Fourierr 發(fā)布于2019-08-14 12:18 / 2274人閱讀

摘要：過程同樣是對(duì)齊相加，不足位補(bǔ)。迭代終止條件是兩個(gè)都為。如果這是一個(gè)類的話該如何實(shí)現(xiàn)將鏈表或者數(shù)組作為成員變量，提供對(duì)其操作的各種方法。

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 復(fù)雜度

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

思路

本題的思路很簡單，按照小學(xué)數(shù)學(xué)中學(xué)習(xí)的加法原理從末尾到首位，對(duì)每一位對(duì)齊相加即可。技巧在于如何處理不同長度的數(shù)字，以及進(jìn)位和最高位的判斷。這里對(duì)于不同長度的數(shù)字，我們通過將較短的數(shù)字補(bǔ)0來保證每一位都能相加。遞歸寫法的思路比較直接，即判斷該輪遞歸中兩個(gè)ListNode是否為null。

全部為null時(shí)，返回進(jìn)位值

有一個(gè)為null時(shí)，返回不為null的那個(gè)ListNode和進(jìn)位相加的值

都不為null時(shí)，返回兩個(gè)ListNode和進(jìn)位相加的值

代碼

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 復(fù)雜度

時(shí)間O(n) 空間(1)

思路

迭代寫法相比之下更為晦澀，因?yàn)樾枰幚淼姆种л^多，邊界條件的組合比較復(fù)雜。過程同樣是對(duì)齊相加，不足位補(bǔ)0。迭代終止條件是兩個(gè)ListNode都為null。

注意

迭代方法操作鏈表的時(shí)候要記得手動(dòng)更新鏈表的指針到next

迭代方法操作鏈表時(shí)可以使用一個(gè)dummy的頭指針簡化操作

不可以在其中一個(gè)鏈表結(jié)束后直接將另一個(gè)鏈表串接至結(jié)果中，因?yàn)榭赡墚a(chǎn)生連鎖進(jìn)位

代碼

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
}

后續(xù) Follow Up

Q：如果將數(shù)字從鏈表改為由數(shù)組表示的話如何解決？
A：迭代寫法仍然可以用于數(shù)組，具體請(qǐng)參見大整數(shù)相加的專題文章。

Q：如果這是一個(gè)類的話該如何實(shí)現(xiàn)？
A：將鏈表或者數(shù)組作為成員變量(member variable)，提供對(duì)其操作的各種方法(method)。