删除链表的倒数第N个节点--哑节点和双指针

0x01.问题

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

C++结构体：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式： ListNode* removeNthFromEnd(ListNode* head, int n)

0x02.简要分析

老样子，单链表访问逆序元素的问题，最好的办法是使用双指针。

在这里一个指针先走n步，然后两个指针一起走，直到快指针走到链表尾。

这里要注意一些特殊情况：

• 如果头节点为空，返回空。
• 如果头节点下一个为空，返回空。
• 如果快指针走了n步后，就走到表尾了，说明要删除第一个元素，返回head->next。

这些特殊情况都要特殊处理。

但我们可以使用哑节点来优化一下，就可以省去这么多没必要的判断。

哑节点其实就是在头节点前面加上一个节点，便于处理头节点的一些特殊情况，省去不必要的代码。返回的时候返回哑节点的下一个节点，也就是头节点，注意吗，不能直接返回头节点，直接返回头节点就失去它存在的意义了，而且会出错。

0x03.解决代码—无哑节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head||!head->next) return NULL;
        ListNode*p1=head;
        ListNode*p2=head;
        for(int i=0;i<n;i++) p1=p1->next;
        if(!p1) return head->next;
        while(p1->next){
            p1=p1->next;
            p2=p2->next;   
        }
        p2->next=p2->next->next;
        return head;
    }
};

0x04.解决代码–使用哑节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next=head;
        ListNode*p1=dummy;
        ListNode*p2=dummy;
        for(int i=0;i<n+1;i++) p1=p1->next;
        while(p1){
            p1=p1->next;
            p2=p2->next;   
        }
        p2->next=p2->next->next;
        return dummy->next;
    }
};

ATFWUS --Writing By 2020–03–23