19-删除链表倒数第N个节点

LeetCode 19. Remove Nth Node From End of List

Given the head of a linked list, remove the n^th^ node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

method: 双指针

维护一个长度为n+1的[left, right]指针，同时移动到right指向最后一个节点，此时left指向倒数第n+1个节点，即可删除倒数第n个节点

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *dummy = new ListNode(0, head);
    ListNode *right = dummy;
    while (n--) right = right->next;
    ListNode *left = dummy;
    while (right->next) {
        right = right->next;
        left = left->next;
    }
    left->next = left->next->next;
    return dummy->next;
}