題目出處
203. Remove Linked List Elements
難度
easy
題目分類
Linked List, Recursion
Linked List remove 操作 part 2
這邊我們要來研究 Linked list 的 remove，
說 remove 其實也不難，最麻煩的應該是要考慮的邊際情況很多，
大觀念來說，我們只要「把下一個 替換成 下下一個」，就可以順利完成，
這觀念聽起來就超簡單的XDDD
但問題就是在要處理一些特殊狀況
這個我們在後續的「邊際問題處理」再來提
個人範例程式碼
我們會習慣宣告假開頭為 dummy，並給予任意值 (這裡給 -1)，
反正我們要用的是 dummy.next 之後的東西，
就當是一種解題習慣吧。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = cur = ListNode(-1)
cur.next = head # start from head, if wrong will pass later
while cur.next: # head exist, we need to parse all Linkedlist
if cur.next.val == val: # check next
cur.next = cur.next.next # pass next (remove)
else:
cur = cur.next # save one ans
head = head.next # move
return dummy.next
Time Complexity
O(n)
Space Complexity
O(1)
算法說明
遍歷一次 head 是一定要的，問題是我們該怎麼移除，
移除的方法我們上面也提到過了，
只需要把「下個」替換成「下下個」就可以輕鬆解決，
只是要多考慮一些「不存在的邊際情況」，這邊我們下面會提。
corner case 特殊情況處理
一同整理在下方「邊際情況處理」
Boundary conditions/ Edge conditions 邊際情況處理
這題問題本身不難，麻煩的是在考慮的邊際情況很多，
這些問題是我自己想的，「一定有些對於讀者來說是可以不用思考的問題」，
總之只要考慮周全就是好方法，不一定要照我的XD
0. (一般情況) 在中間，要移除
沒什麼問題，當 cur.next = cur.next.next 我們就會看到下一個不是的了
-> 我們觀察的值為 (cur.next).val
1. 如果你要移除的，已經是最後一個?
當 cur.next = cur.next.next 我們就會看到 None 了
-> 我們觀察的值為 (cur.next).val
注意：這裡會有個問題可以思考，我們該檢查有沒有值得是 cur.next 還是 cur.next.next?
答案會是 cur.next (也代表指向 this 的 pointer，至於如果是 cur.next.next，可能會因為 cur.next 已經是 None 而跳錯。)
2. 如果最後連續 N 個，都是要移除的?
當 cur.next = cur.next.next ，不斷替換 cur.next 我們遲早就會看到 None 了
-> 我們觀察的值為 (cur.next).val
3. 如果全部都是要移除的?
當 cur.next = cur.next.next 直到我們看到 None，而我們要確保「cur 與 cur 之前的答案都是可行的」
-> 我們觀察的值為 (cur.next).val
4. 如果沒有值?
cur.next 為 None 我們會發現。
5. 如果開頭就是要移除的?
我們的開頭設為「cur.next = head」，也就是說我們只希望讓 cur 之後的答案為正確的。