19. 删除链表的倒数第N个节点（中等）

• 难度: 中等
• 考察: 链表
• 来源: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0019-Remove-Nth-Node-From-End-of-List/Article/0019-Remove-Nth-Node-From-End-of-List.md
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/19.removeNthNodeFromEndofList.md

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路

采取双重遍历肯定是可以解决问题的，但题目要求我们一次遍历解决问题，那我们的思路得发散一下。

我们可以设想假设设定了双指针p和q的话，当q指向末尾的NULL，p与q之间相隔的元素个数为n时，那么删除掉p的下一个指针就完成了要求。

• 设置虚拟节点dummyHead指向head
• 设定双指针p和q，初始都指向虚拟节点dummyHead
• 移动q，直到p与q之间相隔的元素个数为n
• 同时移动p与q，直到q指向的为NULL
• 将p的下一个节点指向下下个节点

关键点

• 双指针

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(1)

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if n == 0 {
        return head
    }
    if head.Next == nil {
        return nil
    }
    
    left := head
	right := head
	gap := 0
	for right.Next != nil {
		right = right.Next
		if gap == n {
			left = left.Next
		} else {
			gap++
		}
	}
    if gap == n {
        left.Next = left.Next.Next
    } else {
        head = left.Next
    }
	return head
}