LeetCode 19 移除链表末尾起第N个节点

1 题目描述

给定一个链表，移除其自末尾起第N个节点后返回该链表。

例子：

输入：给定链表1->2->3->4->5，且n=2

输出：移除链表末尾起第2个节点4后，链表变为1->2->3->5。

题目出处：

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

2 解决思路

两个指针初始均指向链表头部，然后让第一个指针先走N步；

这时，第二个指针开始与第一个指针同时走，当第一个指针到达尾部节点时，第二个指针刚好到达要移除节点的上一个节点。

这样，将第二个指针的下一个节点指向下下个节点即为所求。

注：特殊情况为，第一个指针走了N步时，所指的是尾节点的下一个节点，即nil，这时说明要移除的节点是头节点，该种情况返回头节点的下一个节点即可。

3 golang实现代码

https://github.com/leileiluoluo/leetcode/blob/master/19_Remove_Nth_Node_From_End_Of_List/test.go

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    p, q := head, head
    for ; n > 0; n-- {
        p = p.Next
    }
    if nil == p {
        return head.Next
    }
    for nil != p.Next {
        p = p.Next
        q = q.Next
    }
    q.Next = q.Next.Next
    return head
}