【牛客题霸每日一题】NC53 删除链表的倒数第n个节点 题解

题目链接：https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=117

为了防止删除的是头结点，要在前面加一个哑结点 dummyHead，指向头结点。

先让一个从哑结点开始的指针 cur 向后走n位，然后哑结点指针和该指针 cur 同时右移，直到 cur->next == NULL，此时哑结点指针就走到了倒数第 n 个结点的前一个结点，做删除操作即可。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *cur = dummyHead;
        ListNode *pre = dummyHead;
        while(n--) cur = cur->next;
        while(cur->next) {
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = pre->next->next;
        return dummyHead->next;
    }
};