從LeetCode學演算法 - 70 Linked List (6)

0203. Remove Linked List Elements (Easy)

Question

Remove all elements from a linked list of integers that have value *val *.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

分析/解題

題目要求將一個給定的linked list上值是val的所有元素均去除掉。

前面已經講過一些linked list的題目了，
在處理的重點上，不外乎就是在於如何進行遍歷，
以及移動和取代的不同，是很多人容易弄混的。

我們先假定有一組node的連結長這樣：
prev -> curr -> next

今天如果想要遍歷的話，我們應該做的事情是先宣告一個node，
並將prev的位置指定給node：

1
2
3
4
5
6
Java:
ListNode node = prev;
while (node != null) {
  System.out.println(node.val);
  node = node.next;
}

1
2
3
4
5
Python:
node = prev
while node:
  print(node.val)
  node = node.next

這當中，node = node.next的方式變動了node所指向的記憶體位址，
使其切換到下一個(也就是curr所在的位址)，但prev仍然在原地 。

回歸到題目本身，
題目要求的是跳過特定的val值，例如1->2->6->3，目標val是6。
遇到val值時，應該要將2的連接從6改到3 ，換言之，
當結點node走到2時，發現node.next.val跟目標val一樣，
連接上就會變成：
node.next = node.next.next

此外，為了要進行遍歷，所以每次node都需要往下一個前進，
在前一個狀況下已經確定了會將node.next接到node.next.next去了，
若val不同的話，則需要將node的位置移到下一個 去：
node = node.next

還有一個問題，就是如果一開頭的値就符合val的話，
刪去頭會導致原先的head消失，
為了避免麻煩，常見的做法是宣告一個dummy node，將其連接到head處。
中間不論如何都不去動dummy，結尾時再將dummy.next 回傳即可。

Java的部分，我們初始化一個dummy node並另開一個curr來進行移動。
**每次curr.next的値符合時，就將curr.next接到curr.next.next，
否則就讓curr往下走。**這麼一來，只要不斷檢查curr.next是否為NIL並遞進即可。

Java

Python的部分大同小異。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/ O(1))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

我將於11/26 開設系列同名線上課程**「從Leetcode學演算法｜基礎篇」。** 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
問卷抽書＆取得上架通知： https://pse.is/MS2J2
Leetcode解題挑戰拿優惠： https://pse.is/NAUVP
如果你對線上課程不放心，
也可以先來12/17(二) 我在天瓏分享的講座看看！
講座連結： https://pse.is/JS3LJ