題目鏈接：國際版剃幌，國內(nèi)版
公司：Meta
解法：雙指針
題目描述
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
思路
題目要求我們刪除鏈表的倒數(shù)第 N 個結(jié)點饥漫，并且在 follow up 中明確指出只能用一次遍歷夜郁，因此先完整遍歷一遍鏈表求出鏈表總長度的做法就不可取了同仆。這里我們假設鏈表的總長度是 L丢间，刪除鏈表的倒數(shù)第 N 個結(jié)點惫叛，等同于刪除鏈表的正數(shù)第 L - N 個結(jié)點当凡。我們可以使用快慢指針挤茄，即：快指針先走 N 步如叼，此時慢指針留在頭結(jié)點不動。當快指針走過第 N 個結(jié)點之后穷劈，慢指針再開始移動笼恰。當快指針到達鏈表末尾的時候，慢指針也停止移動歇终，則慢指針停止的位置就是我們想要的結(jié)點社证。
從數(shù)學的角度來看上述思路，可以歸納為：快指針先走了 N 步评凝，則剩余距離為 L - N追葡。之后快慢指針一起走，則快指針到達鏈表末尾的時候奕短，慢指針走過的距離也為 L - N宜肉，而第 L - N 個結(jié)點恰好就是我們想要的那個結(jié)點。復雜度分析也很簡單翎碑，我們通過一次遍歷即得到了解崖飘，并且沒有申請額外的空間，因此時間復雜度為 O(N), 空間復雜度為 O(1)
參考代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 快慢指針, 一個 fast 一個 slow, fast 指針先走 n 步, 之后兩個指針再一起走
slow, fast = head, head
while n > 0:
fast = fast.next
n -= 1
# edge case, 如果 fast 指針已經(jīng)到頭了直接返回 slow 的下一個元素即可
if not fast:
return slow.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head
