【LeetCode 09】19 删除链表的倒数第 N 个结点-阿里云开发者社区

【LeetCode 09】19 删除链表的倒数第 N 个结点

2024-10-14 7

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【LeetCode 09】19 删除链表的倒数第 N 个结点

一、题意

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
   
}

二、思考过程

2.1思路：利用双指针法

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

以上两步的实现：

step1:模拟头节点的创建

typedef struct ListNode ListNode;
    ListNode *shead;
    shead=(ListNode *)malloc(sizeof(ListNode));
    shead->next=head;//虚拟头节点

step2:定义快慢指针

ListNode *SlowIndex=shead;
ListNode *FastIndex=shead;

step3:快指针移动，慢指针同步

while(n--&&FastIndex!=NULL){
        FastIndex=FastIndex->next;
    }
    FastIndex=FastIndex->next;
    while(FastIndex!=NULL){
        FastIndex=FastIndex->next;
        SlowIndex=SlowIndex->next;
    }
    SlowIndex->next=SlowIndex->next->next;//关键之处

step4：返回头指针

return shead->next;

三、完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    typedef struct ListNode ListNode;
    ListNode *shead;
    shead=(ListNode *)malloc(sizeof(ListNode));
    shead->next=head;//虚拟头节点
    ListNode *SlowIndex=shead;
    ListNode *FastIndex=shead;
    while(n--&&FastIndex!=NULL){
        FastIndex=FastIndex->next;
    }
    FastIndex=FastIndex->next;
    while(FastIndex!=NULL){
        FastIndex=FastIndex->next;
        SlowIndex=SlowIndex->next;
    }
    SlowIndex->next=SlowIndex->next->next;
    return shead->next;
}