题目

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

示例 :

1
2
3

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

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

说明 :

1	给定的 n 保证是有效的。

进阶 :

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

分析

一般思路为先用一个指针扫描一遍链表，获取链表长度，然后根据所给的n，再扫描至删除处将节点删除，需要进行两趟扫描，耗时较长。

可以借助两个指针，一趟扫描实现节点删除，思路如下：

在链表的最前面添加一个哑节点（虚拟节点、哨兵节点）dummy，用于处理单个元素链表的特殊情况。

新建两个指针p和q，初始都位于最前端新添加的哑节点处，然后p先移动n步，之后p与q同步移动，直至p到达链表末尾，此时q的下一个节点刚好是需要删除的节点，直接修改q的next指向next的next即可。

qp
↓↓
▢->1->2->3->[4]->5

q     p
↓     ↓
▢->1->2->3->[4]->5

          q      p
          ↓      ↓
▢->1->2->3->[4]->5

          q      p
          ↓      ↓
▢->1->2->3------>5

C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* p = dummy;
        ListNode* q = dummy;
        for(int i=0;i<n;i++)// n若改为n+1，下面应改为while(p)
            p=p->next;
        while(p->next)
        {
            p=p->next;
            q=q->next;
        }
        q->next=q->next->next;
        return dummy->next;// 这里不能是head,当只有一个元素时，就被删除了
    }
};