[LeetCode]19.删除链表的倒数第N个节点

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

思路：

这是一道中等难度的题目。如果可以两次遍历链表的话，最简单的方式就是通过第一次遍历记录链表表长，推算出倒数第 n 个节点的序号，然后通过第二次遍历删掉它即可。

那么如何使用一趟扫描实现这个目的呢？还是可以使用双指针技巧：让快指针 fastCursor 先走n个节点，然后慢指 slowCursor 和快指针 fastCursor 再同时出发，且均在每次循环时前进一个节点。这样就可以使得快指针完成链表遍历时，慢指针刚好停在倒数第n个节点上，这时删去该节点即可。

但事实是我们没有办法直接删去这个节点而同时保持链表的连续，我们必须要停在倒数第n个节点的父节点上。这里有个小技巧：新建一个val = -1的伪头节点dummyHead，通过这个技巧也能保证逻辑一致，且删去原本的头节点而不必单独判断处理。

AC代码：

//扫描两遍的做法
/**
 * 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) {
        if(head == nullptr)
            return nullptr;
        int NodeCounter = 0;
        ListNode* cursor = head;
        while(cursor)
        {
            NodeCounter += 1;
            cursor = cursor->next;
        }
        int LastNode = NodeCounter - n;
        cursor = head;
        if(LastNode == 0)
        {
            ListNode* cursorD = cursor;
            head = cursor->next;
            delete cursorD;
        }
        else
        {
            while(LastNode > 1 && cursor != nullptr)
            {
                LastNode--;
                cursor = cursor->next;
            }
            ListNode* cursorD = cursor->next;
            cursor->next = cursor->next->next;
            delete cursorD;
        }
        return head;
    }
};

//扫描一遍的做法
/**
 * 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) {
        if(head == nullptr || head->next == nullptr)
            return nullptr;
        //新建一个头节点
        ListNode dummyHead(-1);
        dummyHead.next = head;
        ListNode *slowCursor = &dummyHead, *fastCursor = &dummyHead;

        //先走 n+1 个节点
        while(fastCursor != nullptr && n > 0)
        {
            fastCursor = fastCursor->next;
            n--;
        }
        
        //找到倒数第n+1个节点
        while(fastCursor->next != nullptr)
        {
            slowCursor = slowCursor->next;
            fastCursor = fastCursor->next;
        }
        //return slowCursor;
        //删除该节点
        ListNode* tempNode = slowCursor->next;
        slowCursor->next = tempNode->next;
        delete tempNode;
        return dummyHead.next;
    }
};