NC53 #删除链表的倒数第n个节点#

先便利一遍查数，然后再走一遍删节点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        ListNode *pHead = head;
        while(head != nullptr)
        {
            head = head->next;
            count++;
        }
        if(n == count) return pHead->next;
        ListNode *pre = nullptr, *now = pHead;
        for(int i = 1; i < count - n + 1; i++)
        {
            pre = now;
            now = now->next;
        }
        pre->next = now->next;
        return pHead;
    }
};

也可以前后指针，前指针先走k步，然后两个指针一起往前走。
注意处理特殊情况。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pHead = head, *slow = head, *fast = head, *pre = dummy;
        for(int i = 0; i < n; i++)
            fast = fast->next;
        while(fast != nullptr)
        {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = slow->next;
        if(pre == dummy) return dummy->next;
        else return pHead;
    }
};