fuckingAlgorithm【双指针】19.删除链表的倒数第N个结点

19. Remove Nth Node From End of List

remove-nth-node-from-end-of-list

要寻找倒数k个节点，

1. 从虚拟头节点0开始走，p1指针先走k步，到达第k个节点
2. 然后p2指针从虚拟节点0开始，和p1一起同步前进，直到p1走到末尾n+1节点为空，共走了n+1-k步
   p2就达到第n+1-k个了，即倒数第k个

因为
倒数第1个是 正数第n个，即(n+1) - 1个
倒数第2个是正数第n-1个，即(n+1) - 2个
倒数第3个是正数第n-2个，即(n+1) - 3个
。。。。
倒数第k个是正数第n-k+1个，即(n+1) - k个

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{-1, head}
    // 找到倒数n+1个节点，即n个节点前面的一个
    x := findFromEnd(dummy, n + 1)
    x.Next = x.Next.Next
    return dummy.Next
}

func findFromEnd(head *ListNode, k int) *ListNode {
    p1, p2 := head, head
    // 从虚拟头节点0开始移动
    // p1走k步，移动到k个节点
    for i := 0; i < k; i++ {
        p1 = p1.Next
    }
    
    // p1走了N-k+1步，到达第n+1个节点
    // p2走了N-k+1步，到达了n-k + 1 个节点。
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    //p2位于n-k+1个节点，即倒数第k个
    //为倒数第1个为正数第n个节点：n = (n+1) - 1
    //倒数第k个节点： 为正数(n+1) - k
    return p2
}