[数据结构与算法]2021-09-05

链表如何删除节点

删除节点主要思路还是让被删除元素前一个元素指向被删除元素后一个元素，关键点在于找出被删节点的位置。这个可以由双指针算法解决。

由于链表的每个元素（包括开头）都有可能会被删除
所以先设一个虚拟头结点指向head。
@–1--2–3--4–5—6–7--@
f
s
首先定义两个指针first,second。
@–1--2–3--4–5—6–7--@
f
s
然后让first走n步，这里n=4;
然后让f,s一起运动，直到f截至。
@–1--2–3--4–5—6–7--@
f
s
此时s的位置就在n+1的位置。
然后就可以删掉倒数第n个元素了。
例题：leetcode19

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    auto dummy=new ListNode(-1);
    dummy->next=head;
    auto first=dummy,second=dummy;
    while(n--)
    {
        first=first->next;
    }
    while(first->next)
    {
        first=first->next;
        second=second->next;
    }
    second->next=second->next->next;
    return dummy->next;
    }
};