19. Remove Nth Node From End of List.md

19. Remove Nth Node From End of List

思路

题意就是去掉链表中倒数第n个节点。
涉及到链表中倒数节点的思路都是使用两个指针p1、p2，两个指针初始都是head，p2先走n步，然后p1、p2再同时走直到p2到达链尾， 此时p1就位于链表倒数第n个节点的前一个节点。
需要注意当要删除的节点就是head时需要特殊处理。
时间复杂度O(N)，空间复杂度O(1)

C++

/**
 * 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(n <= 0) return head;
        ListNode *p1 = head, *p2 = head;
        while(n--) p2 = p2 -> next;  // p2先走n步
        if(p2 == NULL){ // 此时删掉的应该是head
            head = head -> next;
            delete p1;
            return head;
        }
        while(p2 -> next){
            p1 = p1 -> next;
            p2 = p2 -> next;
        } // 此时p1位于倒数第n个节点的前一个节点
        p2 = p1 -> next;
        p1 -> next = p2 -> next;
        delete p2;
        return head;
    }
};