Leetcode 删除链表的倒数第N个节点

地址：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/42/

题目

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

我的解决方案

常规的方法会想到要计算出链表的长度L，然后再从头结点开始往后遍历L-n-1个结点，即倒数第n个结点的前一个结点，再删除要删除的倒数第n个结点（pre->next = pre->next->next;）。而题目要求用一趟扫描实现，所以需要用到两个指针pre、cur都初始化为指向链表头结点，然后cur指针往后移n个结点到链表的第 n+1 个结点，再把 pre 和 cur 同时往后移直到 cur 的 next 指针指向 NULL ，即 cur 指向链表最后一个结点，此时 pre 指向倒数第 n 个结点的前一个结点，用同样的方法（pre->next = pre->next->next;）删除倒数第 n 个结点即可。

/**
 * 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 *root = head;   //作为返回值
        ListNode *pre = head;
        ListNode *cur = head;
        for (int i = 0; i < n; i++)   //*cur指向第n+1个结点
            cur = cur->next;
        if (cur == NULL)    //说明倒数第n的结点就是头结点
            root = head->next;    //将头指针改为指向第二个节点即可删除头结点
        else {
            while (cur->next != NULL)    //pre和cur同是往后移直到cur指向尾结点
            {
                pre = pre->next;
                cur = cur->next;
            }
            pre->next = pre->next->next;   //删除pre结点的后一个结点，即倒数第n个结点
        }
        return root;
    }
};