首页 > 试题广场 >

删除链表的倒数第n个节点

[编程题]删除链表的倒数第n个节点
  • 热度指数：236105 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: , .
删除了链表的倒数第 个节点之后,链表变为.

数据范围： 链表长度 ，链表中任意节点的值满足 
要求：空间复杂度 ，时间复杂度
备注：
题目保证 一定是有效的
示例1

输入

{1,2},2

输出

{2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
C
左右o头像 左右o
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    struct ListNode* low, *fast, *pre, *p;
    p = pre = low = fast = head;
    int num = 0;
    while (p) {
        num++; // 遍历统计节点个数
        p = p->next;

    }
    if (num < 1 || n == 0) {
        return head;
    }
    if (num == n) {
        return head->next;
    }
    p=head;
    if (n==1) {
        for (int i=0; i<num-2; i++) {
            p=p->next;
       
        }
        p->next=NULL;
        return head;
   
    }
    for (int i = 0; i < n; i++) {
        fast = fast->next;//先让快指针比慢指针走n个位置

    }
    int j = 0;
    while (fast != NULL) {
        fast = fast->next;
        low = low->next; // 当fast节点为空时，low节点即为要删除的节点
        j++; // 记录要删除的节点的位置，以便接下来找到该节点的前驱
       
       

    }
     for (int i=0; i<j-1; i++) {
            pre=pre->next; //找到要删除的节点的前驱结点的位置
       
        }
    pre->next = low->next; // 删除该节点
    return head;
}
编辑于 2023-12-18 23:09:17 回复(0)
C
A202302282044461头像 A202302282044461
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    struct ListNode * p = head;
    struct ListNode * pTemp = NULL;
    int count = 0;
     while (p) {
        p = p->next;
        count++;
     }
     if (count == n) {
        return head->next;
     }
     p = head;
     count = count - n - 1;
     while (count--) {
        p = p->next;
     }
     p->next = p->next->next;
    return head;
}
发表于 2023-09-04 16:26:39 回复(0)
C
无名珠头像 无名珠 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    struct ListNode *phead = (struct ListNode*)malloc(sizeof(struct ListNode)); //设置虚拟头结点
    phead->next = head;
    
    //快慢指针
    struct ListNode *fast = phead;
    struct ListNode *slow = phead;

    for (int i=0; i<n; ++i)
    {
        fast = fast->next;
    }

    while (fast->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;
    return phead->next;
}

发表于 2023-08-19 22:45:46 回复(0)
C
牛客575380960号头像 牛客575380960号
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    // if(head==NULL || n ==0){
    //     return NULL;
    // }
    struct ListNode *p =head ,*q =head;
    for(int i = 1;i <= n;i++){
        q = q->next;
    }
    if(q == NULL){//删除的是第一个节点
        head = p->next;
    }else if(n == 1){//删除的是最后一个节点
        while(p->next->next){
            p = p->next;
        }
        p->next = NULL;
    }else {
        while(q->next){//走到最后一个元素
            q = q->next;
            p = p->next;
        }
        p->next = p->next->next;
    }


    return head;
}
发表于 2023-07-04 11:31:26 回复(0)
C
不放弃的放鸽子能手很想熬夜头像 不放弃的放鸽子能手很想熬夜
新建一个空白头节点，排除被删的结点为初试头节点的错误 
#include <stdlib.h>
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    struct ListNode* new_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    new_head->next = head;
    struct ListNode* p = new_head;
    struct ListNode* q = new_head;
    int sum = 0;

    while (p != NULL)
    {
        sum++;
        p = p->next;
    }
    sum = sum - n - 1;
    while (sum)
    {
        sum--;
        q = q->next;
    }
    q->next = q->next->next;

    return new_head->next;
}


发表于 2023-04-04 19:18:48 回复(0)
C
帅奶哟。头像 帅奶哟。 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    int i = 0;
    struct ListNode *pre = head;    //当前指针的前一个
    struct ListNode *cur = head;    //当前指针
    struct ListNode *nex = head;    //与cur相距n
    //删除第一个结点，直接返回head->next;
    while (pre) {
        i++;
        pre = pre->next;
    }
    if (i == n) {
        head = head->next;
        return head;
    }
    //nex与cur指针相距n
    for (i = 0; i < n; i++){
        nex = nex->next;
    }
    //当nex指向NULL时，cur指向倒数第n个节点
    while (nex){
        pre = cur;
        nex = nex->next;
        cur = cur->next;
    }
    //将倒数第n个节点删除
    pre->next = cur->next;
    return head;
}

发表于 2023-03-19 17:24:15 回复(0)
C
厚礼谢头像 厚礼谢
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here

    if(head == NULL || n == 0)
        return head;

    struct ListNode *p = head;
    struct ListNode *pr = head;
    struct ListNode *pre = NULL;

    for(int i = 0; i < n-1; i++)
    {
        p = p->next;
        if(p == NULL)
            return head;
    }
    while(p->next != NULL)
    {
        p = p->next;
        pre = pr;
        pr = pre->next;
    }
    if(pr == head)
    {
        head = head->next;
        pr->next = NULL;
        free(pr);
    }
    else
    {
        pre->next = pr->next;
        pr->next = NULL;
        free(pr);
    }

    return head;

}
发表于 2022-11-12 21:03:14 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) 
{
    if(!head)
    {
        return NULL;
    }
    struct ListNode *p = head;
    struct ListNode *q = head;
    struct ListNode *prev;
    while(n--)
    {
        q = q->next;
        if(!q && n)
        {
            p = NULL;
            break;
        }
    }
    while(q)
    {
        prev = p;
        p = p->next;
        q = q->next;
    }
    if(p == head)
    {
        prev = p->next;
        p->next = NULL;
        return prev;
    }
    prev->next = p->next;
    return head;
    // write code here
}

发表于 2022-11-02 21:16:50 回复(0)
C
Machinist.头像 Machinist. 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n )
{
    if (head == NULL)
    {
        return head;
    }

    if (head->next == NULL) //只有一个节点
    {
        free(head);
        head = NULL;
        return head;
    }

    int count = 0;
    struct ListNode* cur = head;
    while (cur)
    {
        count++;
        cur = cur->next;
    }
    int k = count - n + 1;  //正着数找到第n个节点

    //头删
    cur = head;
    if (k == 1)
    {
        head = head->next;
        free(cur);
        return head;
    }
    
    //中间删除或尾删
    struct ListNode* prev = NULL;
    for (int i = 1; i < k; i++)
    {
        prev = cur;
        cur = cur->next;
    }

    prev->next = cur->next;
    
    free(cur);
    return head;
}
容易想到的笨方法
发表于 2022-10-26 10:29:20 回复(0)
C
牛客830367735号头像 牛客830367735号
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    struct ListNode *fast,*slow;
    fast=slow=head;
    for(int i=1;i<=n;i++)
        fast=fast->next;
    if(fast == NULL)
        return head->next;
    while(fast->next!=NULL){
        fast = fast->next;
        slow = slow->next;
    }
    //free(slow);
    slow->next = slow->next->next;
    return head;
}
删除完某个节点不应该要free掉吗，为什么加了free不行，不加却可以

发表于 2022-06-06 20:58:06 回复(1)
C
集秋头像 集秋
根据“思路”写成的C语言版本 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    struct ListNode*res=(struct ListNode*)malloc(sizeof(struct ListNode));
    res->next=head;//用res存头结点的位置，以便解决删除头结点的特殊情况
    struct ListNode*fast=head;//快慢指针确定所要删除结点的位置
    struct ListNode*slow=head;
    struct ListNode*pre= res;//pre用来存所要删除结点的前一个结点
    int i=0;
    for(i=0;i<n;i++)
    {
        fast=fast->next;
    }
    while(fast)
    {
        if(fast->next==NULL)
            pre=slow;//pre用来存所要删除结点的前一个结点
        
        fast=fast->next;
        slow=slow->next;
    }
    if(slow->next!=NULL)
    {
        pre->next=slow->next;
        return res->next;
    }
    pre->next=NULL;
    return res->next;
}

发表于 2022-03-24 12:59:00 回复(0)
C
和覅wEJVB头像 和覅wEJVB
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) 
{
    if(head==NULL)
    {
        return head;
    }
    struct ListNode *p1=head;
    int length=0;
    while(p1!=NULL)
    {
        p1=p1->next;
        length++;
    }
    p1=head;//跳出上面循环的时候，p1指向了链表最后的位置，让他重新回到头节点
    int m=length-n;
    if(m<0)
    {
        return head;
    }
    else if(m==0)
    {
        head=head->next;
        return head;
    }
    
        struct ListNode *p2=p1->next;
        for(int i=0;i<m-1;i++)
        {
            p1=p1->next;
            p2=p2->next;
        }
    /*struct ListNde *p3=p2->next;
        p1->next=p3;*/
    /*p1->next=p2->next;*/
    p1->next=p1->next->next;
    //三种删除方法
        free(p2);
        return head;
}
发表于 2022-03-21 08:42:45 回复(0)
C
Chromium丶头像 Chromium丶 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    if(head == NULL) return head;
    struct ListNode *p = head,*pn = head,*pf;
    pf = p;
    for(int i = 0;i<n;i++){
        if(pn) pn = pn->next;
    }
    while(pn){
        pn = pn->next;
        pf = p;
        p = p->next;
    }
    if(pf == p) head = p->next;
    else pf->next = p->next;
    return head;
    // write code here
}

发表于 2022-03-16 16:56:20 回复(0)
C
呸，看见你就开心头像 呸，看见你就开心
//生成一个空结点插入开始；往后找到倒数第n个，连接+删除
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    if(head==NULL || n==0){
        return head;
    }
    struct ListNode *pre = (struct ListNode*)malloc(sizeof(struct ListNode));
    pre->val = -1;
    pre->next = head;
    struct ListNode *p=head,*q=head,*r=pre;
    int i;
    for(i=1;i<n;i++){
        q = q->next;
    }
    while(q->next!=NULL){
        r = r->next;
        p = p->next;
        q = q->next;
    }
    r->next = p->next;
    free(p);
    return pre->next;
}
发表于 2022-03-13 13:38:49 回复(0)
C
牛客503939794号头像 牛客503939794号 
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    struct ListNode *p=head;
    struct ListNode *tmp=head;
    struct ListNode *save=NULL;
    int count=0;
    if(head==NULL)
        return head;
    while(p!=NULL){
        p=p->next;
        count++;
    }
    count=count-n;
    if(count<0){
        return head;
    }else if(count==0){
        head=head->next;
        return head;
    }
    while(count){
        save=tmp;
        tmp=tmp->next;
        count--;
    }
    save->next=tmp->next;
    free(tmp);
    return head;
}

发表于 2022-03-09 22:31:13 回复(0)
C
无敌俊俊头像 无敌俊俊 
typedef struct ListNode Node;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    //求链表的长度
    if(head == NULL)
    {
        return head;
    }
    
    Node *pre = head;
    Node *cur  =pre->next;
     //计算链表的长度
    int len =  0;
    
    while(pre)
    {
        pre = pre->next;
        len++;
    }
    
    pre = head;
    //遍历倒数第n个前面的链表
    int m = len-n;
    if(m<0)
    {
        return head;
    }else if(m==0)
    {
        head = head->next;
        return head;
    }
    //找到倒数第n个结点前面的结点
    m = m-1;
    while(m--)
    {
        pre =  pre->next;
        cur = cur->next;
    }
    Node* next = cur->next;
    //让倒数第n个前面的结点指向倒数第n个后面的那个结点，并删除到时第n个结点
    pre->next = next;
    free(cur);
    
    return head;
}

发表于 2022-03-07 21:45:08 回复(0)
C
yomi——头像 yomi—— 
//快慢指针
快指针先走n步快慢相差N步
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    if(!head)
        return NULL;
    struct ListNode* a=(struct ListNode*)malloc(sizeof(struct ListNode));
    a->next=head;
    struct ListNode* fast=a;
    struct ListNode* slow=a;
    for(int i=0;i<n;i++){
        fast=fast->next;
    }
    struct ListNode* cur=slow;
    while(fast){
        fast=fast->next;
        cur=slow;
        slow=slow->next;
    }
    cur->next=cur->next->next;
    return a->next;
}

发表于 2021-12-08 15:32:51 回复(0)
提交观点

问题信息

链表 双指针
难度：
21条回答 19948浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号