跳轉到

2. Add Two Numbers

題目大意

你將獲得兩個非空的鏈表（linked list），它們各自代表著一個非負整數。其數字以倒序的方式儲存，而每個節點包含一個個位數值。請將這兩個數字相加，並以鏈表的形式返回相加的結果。

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

題目原文連結

範例一
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

範例二
Input: l1 = [0], l2 = [0]
Output: [0]
範例三
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

約束條件

  • 每个鏈接串列（linked list）中的節點數量範圍在 1 到 100 之間。
  • 每個節點（Node）的值在 0 到 9 之間。
  • 保證此鏈接串列所代表的數字不會有前導零。

鏈表的定義

 <?php
 //這是LeetCode針對該題提供的鏈表的定義
 class ListNode {
      public $val = 0;
      public $next = null;
      function __construct($val = 0, $next = null) {
          $this->val = $val;
          $this->next = $next;
     }
  }

解題想法

  1. 根據範例提示，必須將兩個鏈表相加，並且$l1, $l2鏈表中的數字是以倒敘的方式儲存，所以這代表鏈表的最低位為頭部節點，所以如果我們要將兩個相加的話，大概的程式碼如下 
        <?php
    $sum = 0
    while ($l1 !== null || $l2 !== null) {
        if ($l1 !== null) {
            $sum += $l1->val;//取得l1節點值
            $l1 = $l1->next;//移動l1節下一個節點
        }
        if ($l2 !== null) {
            $sum += $l2->val;//取得l2節點值
            $l2 = $l2->next;//移動l2節下一個節點 
        }
    }
  2. 不過還要考慮相加時的進位的問題，必須在下一個節點相加時把進位值補上。

    簡單來說 * intdiv($l1->val + $l2->val, 10); 為整除後的商為進位值 * ($l1->val + $l2->val) % 10 為整除後的餘數為用來回傳的新節點值 

        <?php
    $carry = 0; //進位值

    while ($l1 !== null || $l2 !== null || $carry > 0) {
        $sum = $carry; // 開始前，加上前一個節點的進位值
        if ($l1 !== null) {
            $sum += $l1->val; //取得l1節點值
            $l1 = $l1->next; //移動l1節下一個節點
        }
        if ($l2 !== null) {
            $sum += $l2->val; //取得l2節點值
            $l2 = $l2->next; //移動l2節下一個節點 
        }

        $carry = intdiv($sum, 10); // 整除後的商為進位值
        $newValue = $sum % 10; // 整除後的餘數為新節點值
    }

  3. 輸出要以鏈表的方式返回

    由於LeetCode針對該題提供的鏈表的定義，為單向鏈表結構，所以每個節點只有包含節點的值和一個指向下一個節點的鏈結，這會變成每次新增節點時 需要將鏈表從頭遍歷到最後，才能有辦法找到最後的節點新增，這樣效率下降，為了解決這個問題，必須要有一個參數追蹤鏈表最後一個節點是什麼。

    資料補充-鏈表 

        <?php
    $head = null; // 用來保存頭部第一個節點
    $tail = null; // 用來追蹤鏈表當前最後的節點
    $carry = 0; //進位值

    while ($l1 !== null || $l2 !== null || $carry > 0) {
        $sum = $carry; // 開始前，加上前一個節點的進位值
        if ($l1 !== null) {
            $sum += $l1->val; //取得l1節點值
            $l1 = $l1->next; //移動l1節下一個節點
        }
        if ($l2 !== null) {
            $sum += $l2->val; //取得l2節點值
            $l2 = $l2->next; //移動l2節下一個節點
        }

        $carry = intdiv($sum, 10); // 整除後的商為進位值
        $newValue = $sum % 10; // 整除後的餘數為新節點值

        // 建立用保存節點總和的節點
        $newNode = new ListNode($newValue);

        if ($head === null) {
            //如果是第一個節點，$head和$tail保存同一個節點
            $head = $newNode;
            $tail = $newNode;
        } else {
            // 不是第一個節點的話，把新的節點放在$tail後面
            $tail->next = $newNode;
            $tail = $newNode; // 更新尾節點
        }
    }

自己的答案

<?php
function addTwoNumbers($l1, $l2) {

    $head = null; // 用來保存頭部第一個節點
    $tail = null; // 用來追蹤鏈表當前最後的節點
    $carry = 0; //進位值

    while ($l1 !== null || $l2 !== null || $carry > 0) {
        $sum = $carry; // 開始前，加上前一個節點的進位值
        if ($l1 !== null) {
            $sum += $l1->val; //取得l1節點值
            $l1 = $l1->next; //移動l1節下一個節點
        }
        if ($l2 !== null) {
            $sum += $l2->val; //取得l2節點值
            $l2 = $l2->next; //移動l2節下一個節點
        }

        $carry = intdiv($sum, 10); // 整除後的商為進位值
        $newValue = $sum % 10; // 整除後的餘數為新節點值

        // 建立用保存節點總和的節點
        $newNode = new ListNode($newValue);

        if ($head === null) {
            //如果是第一個節點，$head和$tail保存同一個節點
            $head = $newNode;
            $tail = $newNode;
        } else {
            // 不是第一個節點的話，把新的節點放在$tail後面
            $tail->next = $newNode;
            $tail = $newNode; // 更新尾節點
        }
    }
    return $head; 

}

官方解法

我一直覺得我原本的方法在輸出鏈表時，感覺code有點冗長，去官網看了一下官方提供的解法，發現他在一開始初始化的時候，在迴圈開始前就初始化一個假節點(dummy node)，然後透過另外一個參數追蹤節點尾部，來達到簡化輸出的部分。

官網解法

官網只有提供Python,Java,C++，下面根據邏輯改寫了一份PHP版本的。 

    <?php
    function addTwoNumbers($l1, $l2) {

        $dummy = new ListNode(0);
        $current = $dummy;
        $carry = 0;

        while ($l1 != null || $l2 != null || $carry > 0) {
            $sum = $carry;
            if ($l1 != null) {
                $sum += $l1->val;
                $l1 = $l1->next;
            }
            if ($l2 != null) {
                $sum += $l2->val;
                $l2 = $l2->next;
            }

            $carry = intdiv($sum, 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;
        }

        return $dummy->next;

    }