[数据结构与算法]双指针法去除链表指定位置的节点

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

思路：双指针法，用p指针标记要删除位置，当先指针抵达尾部时，删除p标记的位置节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //虚拟节点用以操作head
        ListNode hair(0,head);
        //快慢指针标记位置
        ListNode *p=&hair,*q=p;
        //制造距离
        while(n-->0){
            if(q->next == nullptr){
                return hair.next;
            }
            q=q->next;
        }
        //标记尾部倒数第k节点
        while(q->next){
            q=q->next;
            p=p->next;
        }
        //指针O（1）时间删除操作，并释放删除节点，避免野指针
        ListNode *tmp=p->next;
        p->next = tmp->next;
        tmp->next = nullptr;
        //返回链头节点
        return hair.next;
    }
};