19. Remove Nth Node From End of List¶
題目¶
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1: 
Example 2:
Example 3:
Constraints: * The number of nodes in the list is sz. * 1 <= sz <= 30 * 0 <= Node.val <= 100 * 1 <= n <= sz
題目大意¶
找尋單linked list的 倒數第 n 個元素並刪除. 返回該 linked list的頭節點
解題思路¶
先讓 fast走 k 步, 然後 fast slow 同速前進 這樣當fast走到nil時, slow所在位置就是在倒數第 k 的節點
來源¶
解答¶
package removenthnodefromendoflist
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type ListNode struct {
Val int
Next *ListNode
}
// 產生 dummyHead,跟 preslow
// 使用雙指針, 先讓 fast走 `k` 步, 然後 `fast slow 同速前進`
// 這樣當fast走到nil時, slow所在位置就是在倒數第 k 的節點
// 將 slow的前一步(preslow)的next 指向 slow.Next
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
dummyHead := &ListNode{Next: head}
preSlow, slow, fast := dummyHead, head, head
for fast != nil {
if n <= 0 {
// 先讓 fast走 `k` 步, 然後 `fast slow 同速前進`
// 這樣當fast走到nil時, slow所在位置就是在倒數第 k 的節點
preSlow = slow
slow = slow.Next
}
n--
fast = fast.Next
}
preSlow.Next = slow.Next
return dummyHead.Next
}