LeetCode19 移除倒數第N個元素
- 2020 年 3 月 5 日
- 筆記
點擊上方藍字，和我一起學技術。
鏈接
https://leetcode.com/problems/remove-nth-node-from-end-of-list
難度
Medium
描述
Given a linked list, remove the n -th node from the end of list and return its head.
給定一個鏈表，要求移除導數第n個元素，並且返回新鏈表的head
樣例:
Given linked list: 1- >2->3->4->5, and _n_ = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
注意:
Given n will always be valid.
給定的n永遠有效
Follow up:
Could you do this in one pass?
你能一發通過么？？？官方嘲諷。
題解
題目的意思非常直白，不需要太多思考就能理解。但是上手去做的話會有一點小問題，因為如果是數組很好辦，我們直接可以求到數組的長度，導數第N個元素也非常容易確定。但是如果是鏈表的話就不同了，因為我們並不知道鏈表的長度，所以沒辦法直接獲取需要刪除節點的位置。
既然直接沒有辦法求到，那麼可以間接去求嘛，所以很自然地可以想到兩次遍歷的方法。
兩次遍歷
這個方法非常直觀，基本上可以說是顧名思義。我們對這個鏈表遍歷兩次，第一次求到鏈表的長度，這樣我們就可以推算到倒數第N個數是正數第幾個數了。第二次我們移動對應的長度，找到需要刪除的節點，將它移除即可。
我們來看下面這張圖，完全可以腦補出演算法：
雖然演算法不難，但是這題當中藏著trick，隱藏了出題人深深的惡意。不相信的話，可以試著不看答案寫寫看，基本上一定會錯上一兩次。原因很簡單，因為會有一些特殊情況需要考慮。
比如，特殊情況1：鏈表當中只有一個元素，顯然這個時候根本不需要移動，也不用刪除，直接return None就好了。但是如果我們使用常規方法的話，是無法刪掉的，必須要特殊判斷這種情況。
特殊情況2：這個要刪的元素剛好是第一個head元素，這種情況也沒有辦法常規解決，也需要特殊判斷。
把這兩個特殊情況考慮到，基本上就沒問題了。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: l = 0 pnt = head # 計算鏈表長度 while pnt: l += 1 pnt = pnt.next # 如果長度為1，直接return None if l == 1: return None # 計算刪除需要移動的長度 l = l - n - 1 # 如果小於0，說明需要刪除第一個元素，那麼直接return head.next。 if l < 0: return head.next pnt = head for i in range(l): pnt = pnt.next pnt.next = pnt.next.next return head
一次遍歷
上面的這種演算法中規中矩，基本上沒有難度。那麼有沒有更好的演算法，比如我們能不能做到只遍歷鏈表一次呢？這樣不就優化了複雜度了嗎？
當然是可以的，說來這種演算法也非常巧妙。如果說我們把鏈表想像成一條跑道，而把移動遍歷的指針想像成跑道上的運動員。我們現在不知道跑道有多長，但是我們想要知道距離終點30米的位置。我們還知道運動員的奔跑速度都一樣。應該怎麼做呢？
我們可以先讓一個運動員先跑30米，然後再派另外一個運動員從起點出發。這樣，當第一個運動員跑到終點的時候，第二個運動員所在的位置就是距離終點30米的位置。
我們把上述的運動員換成指針，跑道換成鏈表，就是這題的解法了。
同樣，我們也有一張圖可以說明：
我們根據描述，可以試著寫出程式碼。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: pnt1 = head # 第一個指針先跑n步 for i in range(n): pnt1 = pnt1.next # 注意，如果是刪除head，會出現跑過頭的情況，需要判斷 if pnt1 is None: return head.next pnt2 = head # 移動第一個指針，直到結尾 while pnt1.next: pnt1 = pnt1.next pnt2 = pnt2.next # 刪除pnt2.next位置的節點 pnt2.next = pnt2.next.next return head
看起來第二種方法似乎更優一些，但實際上如果分析複雜度的話，兩者都是的複雜度，並沒有高下之分。而且比較奇葩的是，我用CPP提交的時候是能明顯感覺出來第二種方法優於第一種幾毫秒的，但是當我換成了Python之後，第二種方法的耗時反而還更長了。可見，快慢都是相對的，一般情況下來說在複雜度相同的情況下，優化常數意義不大。
雖然搞了半天，並沒有什麼效果，但至少我們明白了這點，也算是收穫。
好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支援是我最大的動力。
