[Leetcode]19:Remove Nth Node From End of List

Link : https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Problem :
Given the head of a linked list, remove the nth node from the end of the list and return its head.

給一個linklist head,移除倒數第n個node,回傳linklist head。

圖來自leetcode

Thoughts :
0. 給定快、慢指針,讓快指針找到順著數的第n個node,慢指針不動。
1. 快慢指針一起開始往下走,當快指針走到最後一個node時,慢指針在倒數第n個。
2. 把倒數第n個node進行移除。
3. return head

Solution :

class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
fast = head
slow = head
#快指針走到第n個node
for i in range(n):
fast = fast.next
#此時當快指針走到空的時候代表沒有這個node,直接return
if fast == None:
return head.next
#當快指針還沒有走到最後面的時候,快慢指針都先往下各走一個
while fast.next != None:
fast = fast.next
slow = slow.next
#當快指針走到最後一個node的時候,slow剛好會走到倒數第n個,刪除倒數第n個
slow.next = slow.next.next
return head

# time complexity = O(n), space complexity = O(1)