iT邦幫忙

DAY 10
0

連續30天,挑戰演算法系列 第 10

[Day10] 30 天挑戰演算法 - 兩個 LinkedList 之和

題目來源Add Two Number

問題:
給予兩個 linked lists, 並且在 linked list 裡的所有元素都是正數(沒有負數)而且都是個位數 ,請試著將兩個 linked list 中的數字個別相加到另一個 linked list,若相加超過各位數則進位下至一個節點。

ListNode 定義

public class ListNode {
    public int val {get; set;}
  public ListNode next {get; set;}
  
  public ListNode(int value){
      this.val = value
    next = null;
  }
}

例子
輸入:linked list1: 2 -> 4 -> 3 ; linked list2: 5-> 6-> 4
輸出:7 -> 0-> 8
因為第二個節點 4 + 6 剛好等於 10,所以進位到下一個節點。因此在處理下一個節點時就會多一個進位過來的數字
3 (linked list 1)+ 4(linked list 2) + 1( 第二節點的進位)

想法
兩個 linked list 的節點相加、進位,乍看之下好像很容易,但第一次做起來卻又一堆問題!
我覺得那因為題目沒說兩個 linked list 的節點數目是否相同,所以這兩種可能都必需要考慮進去。否則就會過不了 test case。
因此,我覺的關於這一題的重點應該是計算兩 linked list相加的中止條件。

那麼中止條件是什麼呢?那就要想題目要求什麼?題目給的限制是:

  1. 兩個 linke list 相加
  2. 相加後的值只能是個位數,進位要進到下一個節點

所以兩兩相對應節點相加有值產生可能會遇到情況有

  1. 兩個節點都不為 null
  2. 一個節點是 null
  3. 兩個節點都是 null 但上一個節點相加時 有進位 (進位的值)

那不可能會有值得情況應該是:

  1. 兩個節點都是 null 並且上一節點相加 沒有任何進位

所以根據上面的判斷,我們的中止條件應該是:
Linked list1 的節點 或 Linked list 2 的節點 或 進位的值 皆為 null
換句話說 [ (Linked list1 Node != null) 或 (LinkedList 2 Node != null) 或 (進位值 != 0 ) ]
因此,找到中止條件之後,整個題目就會變得很簡單了,接下來所要的事情就是兩兩相加了!!

虛擬碼

當 ( **節點1 不等於 null** 或 **節點 2 不等於 null** 或 **進位值 不等於 0**)
    節點1+節點2+進位值 assign 給 sum
    從 sum 取得各位數和十位數
    在回傳的 linked list 上新增一節點並且給值為剛取得的 **個位數**
    將剛取得的十位數暫存在 **進位值** 上
    取得節點1的下一個節點 並 assign 給節點1
    取得節點2的下一個節點 並 assign 給節點2
  • 如果你用 Java or Python or C++ 可上 [LeetCode Online Judge][Problem] 驗證

  • 還是想不出來嗎?參考我的答案吧!

    // C# 版本
    public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
    {
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

     int digitInTens = 0;
    
     while (list1Node != null || list2Node != null || digitInTens != 0)
     {
         int sum = 0;
         if (list1Node != null && list2Node != null)
             sum = list1Node.val + list2Node.val + digitInTens;
         else if (list1Node != null)
             sum = list1Node.val + digitInTens;
         else if (list2Node != null)
             sum = list2Node.val + digitInTens;
         else
             sum = digitInTens;
    
         int digitInOnes = sum % 10;
    
         digitInTens = sum / 10;
    
         node.next = new ListNode(digitInOnes);
         node = node.next;
    
         if (list1Node == null)
             list1Node = null;
         else
             list1Node = list1Node.next;
    
         if (list2Node == null)
             list2Node = null;
         else
             list2Node = list2Node.next;
     }
    
     return dummy.next;
    

    }

題外話,雖然寫完了但是程式碼實在太醜了,也很難看得懂,我們來 Refactor 一下吧!
首先呢,先幫程式碼加個註解,以方便抽取我們想要的部份

// 加註解的結果

public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        // 兩個 Linked list 節點相加
        int sum = 0;
        if (list1Node != null && list2Node != null)
            sum = list1Node.val + list2Node.val + digitInTens;
        else if (list1Node != null)
            sum = list1Node.val + digitInTens;
        else if (list2Node != null)
            sum = list2Node.val + digitInTens;
        else
            sum = digitInTens;
                        
        // 取得個位數
        int digitInOnes = sum % 10;
                    
        // 取得十位數
        digitInTens = sum / 10;
        
        // 將個位數新增到結果的 linked list 上
        node.next = new ListNode(digitInOnes);
        node = node.next;

        // linked list 1 取得下一個節點
        if (list1Node == null)
            list1Node = null;
        else
            list1Node = list1Node.next;

        // linked list 2 取得下一個節點
        if (list2Node == null)
            list2Node = null;
        else
            list2Node = list2Node.next;
    }

    return dummy.next;
}

加註解後,就依照各部份使用 Extract Method 取出來吧,讓我們住要的程式碼能夠在同一個表達層級上。

// extract method 後的結果

public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;

        int digitInOnes = GetDigitInOnes(sum);
        
        digitInTens = GetDigitInTens(digitInTens, sum);
        
        node = AddSumToResultLinkedListNode(node, digitInOnes);

        list1Node = GetNextNode(list1Node);
        list2Node = GetNextNode(list2Node);
    }

    return dummy.next;
}

private static ListNode GetNextNode(ListNode node)
{
    // 取得下一個節點
    if (node == null)
        node = null;
    else
        node = node.next;
    return node;
}

private static ListNode AddSumToResultLinkedListNode(ListNode node, int digitInOnes)
{
    // 將個位數新增到結果的 linked list 上
    node.next = new ListNode(digitInOnes);
    node = node.next;
    return node;
}

private static int GetDigitInTens(int digitInTens, int sum)
{
    // 取得十位數
    digitInTens = sum / 10;
    return digitInTens;
}

private static int GetDigitInOnes(int sum)
{
    // 取得個位數
    int digitInOnes = sum % 10;
    return digitInOnes;
}

private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
    // 兩個 Linked list 節點相加
    int sum = 0;
    if (list1Node != null && list2Node != null)
        sum = list1Node.val + list2Node.val;
    else if (list1Node != null)
        sum = list1Node.val;
    else if (list2Node != null)
        sum = list2Node.val;
    else
        sum = 0;

    return sum;
}

有沒有覺的,主要的程式碼變得非常清晰了呢?別忘了在每做一次 Extract Method 後,要跑一下 **Unit Test** 以確保程式沒被改壞掉。 如果你有潔癖的話,還可以繼續處理抽出來的程式碼:

// 完成重構的程式碼,真乾淨
public ListNode addTwoNumbers(ListNode list1Node, ListNode list2Node)
{
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    int digitInTens = 0;

    while (list1Node != null || list2Node != null || digitInTens != 0)
    {
        int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;

        int digitInOnes = GetDigitInOnes(sum);
        
        digitInTens = GetDigitInTens(digitInTens, sum);
        
        node = AddSumToResultLinkedListNextNode(node, digitInOnes);
        node = GetNextNode(node);

        list1Node = GetNextNode(list1Node);
        list2Node = GetNextNode(list2Node);
    }

    return dummy.next;
}

private static ListNode GetNextNode(ListNode node)
{
    // 取得下一個節點
    return (node == null) ? null : node.next;
}

private static ListNode AddSumToResultLinkedListNextNode(ListNode node, int digitInOnes)
{
    // 將個位數新增到結果的 linked list 上
    node.next = new ListNode(digitInOnes);
    return node;
}

private static int GetDigitInTens(int digitInTens, int sum)
{
    // 取得十位數
    return  sum / 10;
}

private static int GetDigitInOnes(int sum)
{
    // 取得個位數
    return sum % 10;
}

private static int CalculateTwoNodeSum(ListNode list1Node, ListNode list2Node)
{
    // 兩個 Linked list 節點相加
    int sum = GetListNodeValue(list1Node) + GetListNodeValue(list2Node);
    return sum;
}

private static int GetListNodeValue(ListNode node)
{
    if (node != null)
        return node.val;
    return 0;
}

哈哈!似乎有點太過分了!!不過,有沒有注意到我的 if - else 都快被我抽光光的!我認為好的程式碼品質就是要項這樣,跟文章一樣讀起來很輕鬆、很愉快!但前提是必序要有 **足夠的** test case, 不然這樣抽,可能一不小心就把城市給搞壞了!!

最後再回顧一下,這時候如果再替程式碼加上註解,是不視覺的有點雞肋了呢?

// 有點雞肋的註解
while (list1Node != null || list2Node != null || digitInTens != 0)
{
    // 兩節點值相加並 加上前一節點的進位值
    int sum = CalculateTwoNodeSum(list1Node, list2Node) + digitInTens;
    // 取得個位數
    int digitInOnes = GetDigitInOnes(sum);
    // 取得十位數
    digitInTens = GetDigitInTens(digitInTens, sum);
    // 將相加的個位數新增至相加結果的 LinkedList 
    node = AddSumToResultLinkedListNextNode(node, digitInOnes);
    node = GetNextNode(node);
    // 取得兩 linked list 的下一節點
    list1Node = GetNextNode(list1Node);
    list2Node = GetNextNode(list2Node);
}

上一篇
[Day09] 30 天挑戰演算法 - 將數字反轉
下一篇
[Day11] 30天挑戰演算法 - 發糖果
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言