[Leetcode] 19. Remove nth node from end of list (删除鏈表的倒數第 N 個節點) 題解紀錄

題目:

Remove nth node from end of list (删除鏈表的倒數第 N 個節點)

難度:

中等

題解思路:

這一題主要是需要使用雙指針來實現

假設 n 是 總長度
假設 k 是 步數

1. 雙指針思路
   
   如果快指針先走 k 步，再讓慢指針和快指針一起走到快指針的底部，這樣子的話，慢指針走到的節點就會是 n-k+1 的節點了，所以這樣子會有兩次迴圈，第一次是走到 k ，第二次是把剩下的長度走完
2. 虛擬頭節點
   
   如上面所說，因為慢指針會走到的節點會是 n-k+1 ，而題目要求我們返回的是
   n-k，所以我們需要使用虛擬頭節點來解決，把 n-k+1 變成 n-k，最後返回虛擬頭節點的資料就可以了

這題的時間複雜度為 O(n)，而空間複雜度也為 O(n)