首页 > 试题广场 >

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

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

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

输入

{1,2},2

输出

{2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Java
一代码夫头像 一代码夫 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     * 1.先获取链表长度，判断n 与长度的关系,如果n >5 ,则返回null
     * 2.通过倒数第n个节点，找出正数第 length-n+1 个节点
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null || n == 0) {
            return null;
        }
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        if (n > length) {
            return null;
        }
        int deleteNode = length - n + 1;
        cur = head;

        if (n == length) {
            return head.next;
        }
        int i = 2;
        while (cur.next != null) {
            if (i == deleteNode) {
                cur.next = cur.next.next;
                break;
            } else {
                cur = cur.next;
            }
            i++;
        }
        return head;
    }
}

编辑于 2023-12-06 15:06:15 回复(0)
Java
阿mini默头像 阿mini默 
public ListNode removeNthFromEnd (ListNode head, int n) {
    // write code here
    if(head == null){
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    for(int i=0; i<n; i++){
        fast = fast.next;
    }
    if(fast == null){
        return head.next;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return head;

}

编辑于 2023-12-05 19:21:58 回复(0)
Java
练习时长两年半的太平湖水怪很理智头像 练习时长两年半的太平湖水怪很理智 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode fast = head;
        // 慢指针用于标记被删除点
        ListNode slow = head;
        // 被删除点的前一个节点
        ListNode pre = new ListNode(-1);
        // 指向头结点
        pre.next = head;
        // 利用快慢指针找到被删除点的位置
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while(fast!= null){
            fast = fast.next;
            slow = slow.next;
            pre = pre.next;
        }
        // slow == head表示被删除点为头节点，删除头节点后，新的头节点为原头结点的下一节点
        if(slow == head) return head.next;
        // 被删除点不是头结点，则将被删除点的前一节点指向被删除点的下一节点，完成指定节点的删除
        pre.next = slow.next;
        return head;
    }
}


发表于 2023-09-25 15:56:58 回复(0)
Java
牛客276339250号头像 牛客276339250号
import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode pre= new ListNode(0);
pre.next=head; //定义一个最慢的指针 ，标记要删除的node的父node
ListNode cur=head;//定义一个慢的指针，标记要删除的node
ListNode fast=head;//定义一个快的指针，标识是否走到链表尾部
ListNode res=pre;//定义一个指针指向最终的链表头
//根据n移动快指针
for(int i=0;i<n;i++){
fast=fast.next;
}
//移动指针
while(fast!=null){
cur=cur.next;
pre=pre.next;
fast=fast.next;
}
//删除node
pre.next=cur.next;
return res.next;
}

}
发表于 2023-09-21 18:10:25 回复(0)
Java
dqxfz头像 dqxfz
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int nSize = 0;
        ListNode prev = dummy;
        ListNode kNode = head;
        while (head != null) {
            if (nSize == n) {
                prev = kNode;
                kNode = kNode.next;
            } else {
                nSize++;
            }
            head = head.next;
        }
        if (kNode != null) {
            prev.next = kNode.next;
        }
        return dummy.next;
    }
发表于 2023-09-08 16:23:55 回复(0)
Java
牛客101757813号头像 牛客101757813号
还得是集合 
public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode nextNode = head;
        List<ListNode> list = new ArrayList<>();
        while(nextNode != null){
            list.add(nextNode);
            nextNode = nextNode.next;
        }
        int len = list.size();
        if(n == len){
            head = head.next;
        }else if(n == 1){
            list.get(len - 2).next = null;
        }else{
            list.get(len - n - 1).next = list.get(len - n + 1);
        }
        return head;
    }


发表于 2023-08-11 19:09:07 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head==null) return null;
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode fast=dummy;//fast从dummy开始走
        while(n-->0){
            fast=fast.next;
        }
        ListNode slow=dummy;//slow从dummy开始走
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        
        ListNode tmp=slow.next.next;
        slow.next=tmp;
        return dummy.next;
    }

发表于 2023-07-18 15:25:12 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        //判断 head == null
        if (head == null) {
            return null;
        }
        //找到倒数第 n + 1个节点
        ListNode fast = head;
        ListNode slow = head;

        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }


        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;

    }
}
发表于 2023-07-10 12:41:37 回复(0)
Java
像素射手头像 像素射手 
public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode vHead = new ListNode(-1);
        vHead.next = head;
        int length = 0;
        for(ListNode p = head; p != null; p = p.next){
            length ++;
        }
        ListNode pre = vHead;
        ListNode cur = head;
        for(int i = 0; i < length - n; i++){
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = cur.next;
        cur = null;
        return vHead.next;
    }

发表于 2023-07-05 17:34:29 回复(0)
Java
谦虚的共享单车人躺平又起来了头像 谦虚的共享单车人躺平又起来了 
public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head.next == null && n == 1) return null;
        ListNode dummy = new ListNode(0) ,pre = head , cur = head , temp = dummy;
        dummy.next = head;

        //先让右指针走n步,当右指针为null的时候说明没有倒数第n个节点
        for (int i = 0; i < n; i++) {
            if(cur == null) return head;
            cur = cur.next;
        }
        //找到要删除的节点
        while(cur != null){
            cur = cur.next;
            temp = temp.next;
            pre = pre.next;
        }

        //进行删除
        temp.next = pre.next;
        return dummy.next;
    }

发表于 2023-06-27 10:35:18 回复(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
        ListNode p=head;
        ListNode q=head;
        int num=0;
        while(p!=null){
            num++;
            p=p.next;
        }
        if(num==n) return head.next;
        for(int i=0;i<num-n;i++){
           
            if(i+1==num-n) q.next=q.next.next;
            q=q.next;
        }
        //q.next=q.next.next;
        return head;
    }
}
发表于 2023-05-23 08:47:11 回复(0)
Java
卤蛋twb头像 卤蛋twb
// 倒数第K个节点的解题思想，但是防止会删除头节点，所以搞了一个虚拟头节点，让slow指到倒数第K+1个节点就行了

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;
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode fast = res;
        ListNode slow = res;

        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 res.next;
    }
}
发表于 2023-04-26 21:35:02 回复(1)
Java
牛客725140028号头像 牛客725140028号
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
        List<ListNode> list = new ArrayList<>();
        ListNode pHead = head;
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        if (list.size() - n == 0) {
            ListNode target = list.get(list.size() - n);
            ListNode temp = target.next;
            target.next = null;
            pHead = temp;
            return pHead;
        } else {
            ListNode target = list.get(list.size() - n);
            ListNode pre = list.get(list.size() - 1 - n);
            ListNode temp = target.next;
            target.next = null;
            pre.next = temp;
            return pHead;
        }

    }
}
发表于 2023-03-26 16:57:29 回复(0)
Java
jwhan99头像 jwhan99 
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) {
        if (n == 0) {
            return head;
        }
        // write code here
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            length++;
        }
        if (length == n) {
            return head.next;
        }
        // n一定是有效的，只需移动到倒数第n个元素之前即可
        int counter = 0;
        temp = head;
        while (temp != null) {
            if (length - counter == n + 1) {
                // 找到了倒数第n个元素的前一个元素
                temp.next = temp.next.next;
                return head;
            }
            temp = temp.next;
            counter++;
        }
        return head;
    }
}

发表于 2023-03-22 21:19:35 回复(0)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    /**
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        List<Integer> list = new LinkedList();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        if (list.size() == 1) return null;
        list.remove(list.size() - n);
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        for (int i = 0; i < list.size(); i++) {
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        return sentinel.next;
    }
}

发表于 2023-03-18 02:14:05 回复(0)
Java
kareni头像 kareni
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) {
        if (head == null) {
            return null;
        }
        int index = 1;
        ListNode left = head, cur = head, right = head;
        while (right.next != null && index < n) {
            right = right.next;
            index++;
        }
       

        while (right.next != null) {
            right = right.next;
            left = cur;
            cur = cur.next;
        }
       
        if (cur == head) {
            head = head.next;
        } else {
            left.next = cur.next;
            cur.next = null;
        }
       
        return head;
    }
}
发表于 2023-02-07 10:40:12 回复(0)
Java
ZhanHeng头像 ZhanHeng 
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) {
        if (head == null || head.next == null) {
            return null;
        }
        // 获取链表长度
        int len = 1;
        ListNode tmp = head;
        while (tmp.next != null) {
            ++len;
            tmp = tmp.next;
        }
        // 倒数第n个节点，正着数是第(len-n+1)个节点
        int targetIndex = len - n + 1;
        ListNode pre = head;
        ListNode p = head;
        // 若命中且为第1个则直接跳过第1个节点，并返回
        if (targetIndex == 1) {
            p = p.next;
            pre = pre.next;
            return pre;
        }
        int count = 1;
        while (p.next != null) {
            ++count;
            if (count == targetIndex) {
                p = p.next;
                pre.next = p.next;
                p.next = null;
                break;
            } else {
                p = p.next;
                pre = p;
            }

        }
        return head;
    }
}

发表于 2022-12-14 16:19:56 回复(0)
Java
GoIn头像 GoIn 
import java.util.*;

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

import java.util.*;
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        //链表为空,直接返回null
        if(head == null){
            return null;
        }
        //定义一个新的头结点
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode cur = newHead;

        //定义一个queue存储节点
        LinkedList<ListNode> queue = new LinkedList<>();
        while(cur != null){
            //每次都将当前节点存储到queue最前面
            queue.addFirst(cur);
            cur = cur.next;
        }
        ListNode temp = null;
        //循环n+1次得到删除节点的前一个节点
        for(int i = 0;i<=n;i++){
            temp = queue.getFirst();
            queue.removeFirst();
        }
        //将待删除节点的的next指向删除的下一节点
        temp.next = temp.next.next;
        return newHead.next;
    }
}

发表于 2022-12-07 16:46:18 回复(0)
Java
牛客375488447号头像 牛客375488447号 
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 res = new ListNode(-1);
        res.next = head;
        // 前指针
        ListNode pre = res;
        // 后指针
        ListNode after = res;
        int count = 0;
        while(after != null){
            if(count == n){
                while(after.next != null){
                    pre = pre.next;
                    after = after.next;
                }
                pre.next = pre.next.next;
            }
            after = after.next;
            ++count;
        }
        return res.next;
    }
}

发表于 2022-11-18 11:15:34 回复(0)
Java
小杨yyy头像 小杨yyy
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 || head.next==null){
            return null;
        }//长度为1或者为0,删除后肯定为空，直接返回null
        int length=0;
        ListNode saveHead=head;
        while(saveHead!=null){
            saveHead=saveHead.next;
            length++;
        }//计算链表长度

        if(n==length){
            return head.next;
        }//如果删除的节点为第一个节点，无法找到他的前一个结点，直接单独处理，返回head.next即可

        ListNode lastNPre=findLastNPre(head,n);//其余情况通过找到lastPre节点处理
        if(lastNPre.next.next!=null){
            lastNPre.next=lastNPre.next.next;
        }else{
            lastNPre.next=null;
        }
        
        return head;

    }
    public ListNode findLastNPre(ListNode pHead,int k){
        //找到要删除的节点的前一个结点
        if (pHead == null)
            return pHead;
     
        ListNode p=pHead;
        ListNode q=pHead;
        while(k>0){
            if(p==null){
                return null;
            }
            p=p.next;
            k--;
        }
        ListNode temp=pHead;
        while(p!=null){
            p=p.next;
            q=q.next;
        }
        while(temp.next!=q){
            temp=temp.next;
        }
        return temp;
    }
}
发表于 2022-11-09 17:09:04 回复(0)
提交观点

问题信息

链表 双指针
难度：
100条回答 19951浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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