首页 > 试题广场 >

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

[编程题]删除链表的倒数第n个节点

热度指数：245274 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，

给出的链表为: $1\to 2\to 3\to 4\to 5$ , $n= 2$ .
删除了链表的倒数第 $n$ 个节点之后,链表变为 $1\to 2\to 3\to 5$ .

数据范围：链表长度 $0\le n \le 1000$ ，链表中任意节点的值满足 $0 \le val \le 100$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$
备注：

题目保证 $n$ 一定是有效的

示例1

输入

{1,2},2

输出

{2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

牛客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)

Java

毛豆来啦

方案:跟找到倒数第k个节点有所不同,主要是需要设置一个虚拟节点,用来记录第k个节点的前一个节点.

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        //需要设置一个虚拟节点
        ListNode v = new ListNode(-1);
        //虚拟节点指向头结点
        v.next = head;
        //使用双指针的方案
        ListNode last = head;
        ListNode nodeN = v;
      
        int index = 1;
        while(last != null){
            last = last.next;
            if(index > n) nodeN = nodeN.next;
            index ++;
        }
        //执行删除操作
        ListNode temp = nodeN.next;
        nodeN.next = temp.next;

        return v.next;
    }
}

发表于 2022-04-30 15:28:21 回复(0)

C++

forestjylee

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode *dummy_head = new ListNode(-1);
        dummy_head->next = head;
        
        ListNode *fast=head, *slow=dummy_head;
        
        while(n) {
            fast = fast->next;
            --n;
        }
        
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy_head->next;
    }
};

dummy_head简化条件判断

slow-->next指向实际需要删除的节点，节省一个中间变量

发表于 2022-02-10 11:43:32 回复(0)

蒙蒙D

func removeNthFromEnd( head *ListNode ,  n int ) *ListNode {
    // write code here
    var (
        fast *ListNode = head
        slow *ListNode = head
        pre *ListNode    
        )
//     if n <=0 {
//         return head
//     }
    for i:= 0 ; i < n-1 ; i++{  
        fast = fast.Next
//         if fast.Next == nil{
//             break
//         }
    }
    for fast.Next != nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next
    }
    if pre == nil {
        return head.Next
    }else{
        pre.Next = slow.Next
    }
    return head
}

发表于 2021-12-14 07:35:27 回复(0)

倔强小头

//就是一个走到n位置，另一个和他一起走，那么就倒数了
public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode node=head;
        ListNode fast=head;
        int count=0;
        while (count<n){
            fast= fast.next;
            if(fast==null) return head.next;
            count++;
        }
        while (fast.next!=null){
            fast=fast.next;
            node=node.next;
        }
        node.next=node.next.next;
        return head;
    }

发表于 2021-12-02 15:54:18 回复(0)

Javascript

♈FourBrother✅已认证♉

// 将链表各个节点的顺序存入map对象中，然后找到倒数第n - 1和倒数第n+1个进行连接操作

function removeNthFromEnd( head ,  n ) {
    // write code here
    const map = new Map()
    let cur = head
    let i = 0
    while (cur) {
        map.set(i, cur)
        i ++
        cur = cur.next
    }
    
    const pre = map.get(i - n - 1)
    const next = map.get(i - n + 1)
    if (!pre) return head.next
    pre.next = next
    return head
}

发表于 2021-11-18 16:53:42 回复(0)

Java

Carmen-Xiao

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode cur=head;
        ListNode fast=head;
        for(int i=0;i<n;i++){
            fast=fast.next;
            if(fast==null) return head.next;
        }
        while(fast.next!=null){
            cur=cur.next;
            fast=fast.next;
        }
        cur.next=cur.next.next;
        return head;
    }
}

发表于 2021-11-15 21:59:56 回复(0)

12枚硬币

题目有问题吧，双指针法的时间复杂度是O(N)，N是链表总长度。时间复杂度O(n)能做到吗？😅

发表于 2021-08-28 16:13:56 回复(0)

C++

恨别鸟惊心

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int i, length = 0;
        struct ListNode* L; //返回表
        struct ListNode* c; //用于遍历链表求表长
        struct ListNode* pre; //工作指针前驱
        struct ListNode* p; //工作指针
        struct ListNode* q; //释放被删节点
        if(head == NULL || head->next == NULL){ //表为空或仅有1个结点，必然返回空表
            return NULL;
        }else {
            pre = head;
            c = head;
            L = head;
            p = head->next;
            while(c != NULL){
                length++; //求表长
                c = c->next;
            }
            if(n == length){ //删除首节点，
                q = pre;
                L = L->next;
                free(q);
                return L;
            }else{ //删除非首节点
                for(i = 1; i < length - n; i++) //将p指向需删结点，pre作为前驱跟随
                {
                    pre = pre->next; 
                    p = p->next;
                }
                if(p->next == NULL){ //若为尾节点，直接将pre指针域置空
                    q = p;
                    pre->next = NULL;
                    free(q);
                }else{ //非尾节点普通删除方法
                    q = p;
                    p = p->next;
                    pre->next = p;
                    free(q);
                }
            }
        }
        return L;
    }

发表于 2021-08-27 18:32:27 回复(0)

C++

分生乏术

//必须要考虑到内存的释放，要不然手撕代码可能被鄙视

ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if(NULL == head || n <= 0)
            return NULL;
        ListNode* first = head;
        ListNode* last = head;
        for(int i=1; i < n ;i++)
        {
            last = last->next;
            if(last == NULL)
                return NULL;
        }
        //链表长度就为n，删除首结点
        if(last->next == NULL)
        {
            //占存不用的结点，好释放   
             ListNode* temp = head->next;
            delete(head);
            return temp;
        }
                //last往后移动一个单位这样下一次first就可以少移动一个
        last = last->next;
        //如果链表长度＞n
        while(last->next != NULL)
        {
            last = last->next;
            first = first->next;
        }
                //占存结点并释放。不能直接释放first->last，会出错的的。
        ListNode* temp = first->next;
        first->next = first->next->next;
        delete(temp);
        return head;
    }

发表于 2021-08-25 17:14:03 回复(0)

C/C++

牛客381893504号

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if (nullptr == head) return nullptr;
       if (0 == n)          return head;
       ListNode *dummy = new ListNode(0);
       dummy->next= head;
       int deleteIndex =  sizeOfLinkedListWithListNode(head) - n;
       ListNode*cur = dummy;
       for (int i=1; i<= deleteIndex ;++i) {
           cur = cur->next;
       }
       cur->next = cur->next->next; 
       ListNode* ans = dummy->next;
       return ans;
    }
    
    int sizeOfLinkedListWithListNode(ListNode* head) {
        if(nullptr == head) return 0;
        ListNode* cur = head;
        int size = 0;
        while(cur) {
            size++;
            cur = cur->next;
        }
        return size;
    }
};

思路1: 删除链表倒数第k个节点，第一步获取链表的长度length,转化为删除正向第length-k序号对应的元素，比如1 2 3 4 5，删除倒数第二个元素即4，也就是正常找到序号为3（length - 2）值为3的节点，将3的next指针指向5节点，然后销毁4节点即可

发表于 2021-04-20 13:40:54 回复(0)

肥猿

思路：先从头节点开始走n步，然后再找另一个节点从头节点开始走，

前后两个节点同时走，确定倒数第n个节点的位置，然后进行删除

public class Solution {

/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode cur=head;
ListNode help=head;
ListNode pre=head;
while(n--!=0){
pre=cur;
cur=cur.next;
}
if(cur==null){
return head.next;
}
while(cur!=null){
pre=help;
help=help.next;
cur=cur.next;
}
pre.next=help.next;
return head;
}
}

发表于 2021-03-13 13:09:00 回复(0)

C/C++

一个好听的名字

试图不用双指针，用大空间来换时间，不过最后还是3ms没能到2ms。

用map来记录位置和对应的节点，倒数转换为正数，直接取值，去节点。（首节点单独处理）

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        int len_List = 0;
        map<int, ListNode*> index_node;
        ListNode* temp = head;
        while (temp != NULL) //放进map里，长度查询好了
        {
            index_node[len_List + 1] = temp;
            len_List++;
            temp = temp->next;
        }
        if (n == len_List)  //如果是第一位
            return head->next;
        int index = len_List - n; //查询正确的map位置
        temp = index_node[index];
        temp->next = temp->next->next;
        return head;
    }
};

编辑于 2021-01-19 10:40:43 回复(0)

坎波帝哥拉

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // write code here
    ListNode *pos=head;
    ListNode *prev=NULL;
    ListNode *res=head;
    while(n--)
    {
        pos=pos->next;
    }
    while(pos)
    {
        prev=res;
        res=res->next;
        pos=pos->next;
    }
    if(prev==NULL) return res->next;
    prev->next=res->next;
    return head;
}

简洁的快慢指针法

发表于 2020-12-17 21:08:02 回复(0)

Java

执子一白

整体思路并不复杂，使用双指针标记即可，
难点在于要理清楚，距离和循环边界条件
及注意特殊情况，删除头节点时的处理

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head==null){
            return null;
        }
        //新 new 一个节点指向头节点，为待删节点前一个节点
        ListNode preNeedDel=new ListNode(0);
        preNeedDel.next=head;
        //标记需要删除的节点
        ListNode needDel=head;
        //标识最后一个节点
        ListNode end=head;
        //标识删除的倒数第 n 个节点
        int i=0;

        while(end!=null){
            //先拉开 n 个距离 注意这里 end 会走到 null
            if(i<n){
                end=end.next;
                i++;
            }else{
                end=end.next;
                preNeedDel=preNeedDel.next;
                needDel=needDel.next;
            }
        }
        preNeedDel.next=preNeedDel.next.next;
        //注意删除头节点情况
        if(needDel==head){
            return  preNeedDel.next;
        }
        return head;
    }
}

编辑于 2020-11-29 10:10:18 回复(0)

Java

tornado123

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode root = new ListNode(-1);
        root.next = head;
        // 方便处理头节点的删除
        ListNode pi = root, pk = root;
        // 先使 pi 前进 n 步，确保 pk 和 pi 相差 （n），当 pi 走到末尾的时候，pk 就是倒数第 n + 1 个节点,直接删除pk后面的节点即可
        for(int i = 0; i < n; i++) {
            pi = pi.next;
        }
        while(pi.next !=  null) {
            pi = pi.next;
            pk = pk.next;
        }
        // 删除 pk 后面的节点
        pk.next = pk.next.next;
        return root.next;
    }
}

发表于 2020-11-26 10:24:02 回复(0)

狼201807081031441

ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
if (head == NULL) {
          return NULL;
      }

ListNode* leader = head;
ListNode* slow = head;

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

if (leader == NULL) {
          return head->next;
      }

while (leader->next) {
leader = leader->next;
slow = slow->next;
}

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

发表于 2020-10-12 18:03:26 回复(0)

自律

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 为了防止是删除第一个节点 所以增加一个新的节点指向头结点
        ListNode* hh = new ListNode(-1);
        hh->next = head;
        int len = 0;
        ListNode* pre = head;
        while(pre != nullptr)
        {
            len++;
            pre = pre->next;
        }
        // 得到删除节点的前一个节点的位置
        int erase_idx = len - n;
        
        if(len == 1) return nullptr;
        
        pre = hh;
        // 移动到删除节点的头一个节点的位置
        for(int i = 0; i < erase_idx; i++) pre = pre->next;
        // 进行删除操作
        pre->next = pre->next->next;
        //返回值
        return hh->next;
    }
};

发表于 2020-09-03 15:35:11 回复(0)

C/C++

漫漫云天自翱翔

/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
ListNode* first=head;
ListNode* second=NULL;
for (int i = 0; i < n; ++i) {
first = first->next;
}
if (first == NULL) {
//不需要删除
return head->next;
}
second=head;
while (first->next != NULL) {
first = first->next;
second = second->next;
}
if(second){
first=second->next;
second->next=second->next->next;
}else{
//倒数N为头节点，需要删除头节点；
first=head;
head->next=head->next->next;
}
delete(first);
first=NULL;
return head;
}
};

发表于 2020-08-31 14:10:05 回复(0)

风中追风20180314092925

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if(head == nullptr || n < 1) return NULL;
    ListNode *newHead = new ListNode(-1);
    newHead->next = head;
    ListNode *front = newHead, *pre = NULL, *cur = newHead;

    while (n--)
        front = front->next;
    while (front) {
        front = front->next;
        pre = cur;
        cur = cur->next;
    }

    if(cur->next)
        pre->next = cur->next;
    else
        pre->next = NULL;

    return newHead->next;
}

发表于 2019-05-07 20:57:02 回复(0)