iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 23

【從面試題學邏輯-23】!吧字數加相來過倒著試(leetcode 2. Add Two Numbers )

題目:
請寫一個方法,加總兩個LinkedList中的數字後,用LinkedList的方式傳回去
傳進來的數字是倒過來的,傳回去也要是倒過來的
(CTCI 2.5也是這題喔)

舉例:
假設輸入是3→2→1和7→6→5→4
就是123+4567
結果應該是4690,必須傳回0→9→6→4

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


這一題最暴力解就是把兩條LinkedList硬讀出來,加起來再轉成另一個LinkedList傳回去,但這種暴力法我們就不多說啦

那我們要怎麼邊讀邊產生結果的LinkedList呢?

這題有兩個問題要解決

  1. 遇到進位時要額外處理
  2. 兩條LinkedList長度可能不同

進位時的額外處理,我們可以用一個int來作保留,也就是這個int負責處理位數相加的結果

什麼意思呢?假設今天進來5和6兩個數,我們把相加的結果,也就是11,先加到這個int中。接著我們取這個int的個位數,製作成一個新的Node,然後把這個int除10,變成十位數。如果一來,進位就會保持在int中,這樣子就可以把進位帶到下一位的運算之中

而LinkedList長度不同的問題,我們可以用「有下一個再讀」來處理,也就是有下一個Node時,再把結果加到上面提的int之中,沒有就不理他

好像有點抽象,我們直接看程式碼做解說吧

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode CurrentNode = head;
        int sum=0;
        while(l1!=null||l2!=null||sum!=0) {
            if(l1!=null) {
                sum+=l1.val;
                l1=l1.next;
            }
            if(l2!=null) {
                sum+=l2.val;
                l2=l2.next;
            }
            CurrentNode.next = new ListNode(sum%10);
            CurrentNode=CurrentNode.next; 
            sum/=10;
        }
        return head.next;
    }
}
ListNode head = new ListNode(0);
ListNode CurrentNode = head;
int sum=0;

首先我們開個head的Node當解答LinkedList的頭,接著用CurrentNode指向head,來幫我們指出下一個答案,要加到哪個Node後面

sum就是我們上面所說,幫忙處理加總的int

while(l1!=null||l2!=null||sum!=0)

這段程式碼就是當兩條LinkedList還沒讀取完時會繼續執行,而且sum不等於0時也會繼續執行

什麼情況下都讀取完了sum還會不為0?就是需要進位的時候喔

if(l1!=null) {
    sum+=l1.val;
    l1=l1.next;
}
if(l2!=null) {
    sum+=l2.val;
    l2=l2.next;
}
CurrentNode.next = new ListNode(sum%10);
CurrentNode=CurrentNode.next; 
sum/=10;

這裡就是當l1、l2分別沒讀取完時,就再把下一個Node讀進來,同時把數字加進sum中。因為我們是分開讀取,如果LinkedList讀完了,就不會再讀下一個Node,所以不會產生讀不到東西的錯誤

最後製作新的Node,並且把sum除以10(上面說到的處理進位問題)

解決!


上一篇
【從面試題學邏輯-22】如何邊拉著狗狗跑步邊刪Node?(leetcode 19. Remove Nth Node From End of List )
下一篇
【從面試題學邏輯-24】 如何製作能馬上找到最小值的stack?(leetcode 155. Min Stack)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言