LeetCode#203-Remove Linked List Elements-移除鏈表元素

• 2020 年 4 月 11 日
• 筆記

一、題目

刪除鏈表中等於給定值 val 的所有節點。

示例:

輸入: 1->2->6->3->4->5->6, val = 6  輸出: 1->2->3->4->5  

二、題解

• 解法1：哨兵節點。

初始化一個哨兵節點 solider，並將其 next 指針指向鏈表的頭部；
初始化一個指針 prev 指向哨兵節點 solider，作為前繼節點；

比較前繼節點的下一個節點和要刪除的節點，若下一個節點是要刪除的節點，則 prev->next = prev->prev->next，反之則前繼節點移動到下一個節點，即 prev = prev->next；

最後返回 solider->next。

時間複雜度：O(n)；空間複雜度：O(1)。

class ListNode {      public $val = 0;      public $next = null;      function __construct($val) {          $this->val = $val;      }  }    /**   * @param ListNode $head   * @param Integer $val   * @return ListNode   */  function removeElements($head, $val) {      $solider = new ListNode(null);      $solider->next = $head;        $prev = $solider;      while ($prev->next!= null) {          if ($prev->next->val == $val) {              $prev->next = $prev->next->next;          } else {              $prev = $prev->next;          }      }        return $solider->next;  }  

• 解法2：不設置哨兵節點（虛擬頭節點）

上面的解法是設置了一個虛擬頭節點，那如果不設置虛擬頭節點呢？

先判斷鏈表的頭節點是不是要刪除的值，如果是，則將頭節點向後移動，若移動完後頭節點為空，則說明該鏈表的所有節點均為要刪除的；

設置一個前繼節點 prev，並指向頭節點，比較前繼節點的下一個節點的值和要刪除的值，若相等，則將前繼節點的下一個節點指向前繼節點下一個節點的下一個節點，反之則前繼節點向後移動；

最後返回 head 即可。

function removeElements($head, $val) {      //如果開頭就是要刪的元素，則將頭節點移動      while ($head->val == $val) {          $head = $head->next;      }        //如果鏈表全是要刪除的元素，則頭節點經過上述操作後為空      if ($head == null) {          return null;      }        $prev = $head;      while ($prev->next!= null) {          if ($prev->next->val == $val) {              $prev->next = $prev->next->next;          } else {              $prev = $prev->next;          }      }        return $head;  }