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;  }