思路

链表题三套路:哑结点,栈,快慢指针

用栈的话空间复杂度会比较高

这题就用哑结点dummy和快慢指针来实现

1
2
3
哑结点是防止特殊情况,把头结点删除了
因为删除一个结点我们需要知道它的前驱结点就可以了
先让slow指向dummy,fast指向head,等下要让他们一起走,让slow最终指向删除结点的前驱节点,因此fast的位置得找好,先让fast到开始往后n处

while(fast)这样slow就刚好到达删除结点的前一个结点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode*dummy=malloc(sizeof(struct ListNode));
    dummy->val=0;
    dummy->next=head;
    struct ListNode*slow=dummy;
    struct ListNode*fast=head;
    for(int i=0;i<n;i++){
        fast=fast->next;
    }
    while(fast){
        fast=fast->next;
        slow=slow->next;
    }
    slow->next=slow->next->next;
    return dummy->next;
}

image-20241104103714761