我要招人

去企业版

首页 > 试题广场 >

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

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

热度指数：236105 时间限制：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，点此查看相关信息

算法知识视频讲解

Javascript

牛客180842365号

function removeNthFromEnd( head , n ) {
// write code here
// 得到链表的长度
if(!head) return
let l = 0
let p = head
while(p) {
l++
p = p.next
}
p = head
if(l-n-1 >= 0)
{
for(let i = 0; i < l - n - 1; i++)
{
p = p.next
}
if(p === null) return head.next
if(p.next)
{
p.next = p.next.next
}
else
{
return null
}
return head
}
else
{
return head.next
}
}

发表于 2022-08-03 14:18:42 回复(0)

Javascript

韦泽杨

// 基于哨兵(假头节点) 节点的双指针方法 
// 双指针
let removeNthFromEnd = (head, n)=>{
    let fakeHead = {next: head}, p1 = fakeHead, p2 = fakeHead;
    while (p2 && n+1 > 0){
        p2 = p2.next;
        n--;
    }
    while (p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    p1.next = p1.next.next;
    return fakeHead.next;
}

module.exports = {
    removeNthFromEnd : removeNthFromEnd
};

发表于 2022-01-05 20:11:17 回复(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)

Javascript

牛客449648190号

function removeNthFromEnd( head ,  n ) {
    let dummy = new ListNode(0);
    dummy.next = head;
    
    let length = 0;
    while(head){
        length++;
        head = head.next;
    }
    
    let curr = dummy;
    for(let i =1;i<length-n+1;i++){
        curr = curr.next;
    }
    curr.next = curr.next.next;
    
    return dummy.next;
}
module.exports = {
    removeNthFromEnd : removeNthFromEnd
};

时间复杂度和空间复杂度双低，有什么改进方法吗？

发表于 2021-10-24 16:52:58 回复(0)

Javascript

飞牛cz

发表于 2021-10-12 00:08:49 回复(0)

Javascript

四季奶青七分甜

function removeNthFromEnd( head ,  n ) {
    // write code here
  if(head==null)return head
  let newhead = new ListNode(0)
  newhead.next = head
  head = newhead
  let slow = head,fast = head
  let i=0;
  while(fast){
    if(i>n){
      slow = slow.next
    }
    fast = fast.next
    i++
  }
  slow.next = slow.next.next
  return newhead.next
}

发表于 2021-08-09 15:35:41 回复(0)

JavaScript

一直赢好无奈

这个代码应该是最短的了吧:

export function removeNthFromEnd(head: ListNode, n: number): ListNode {
    let first = {next : head} , cur = first , slow = first;
    do{ if(n-- < 0) slow = slow.next; } while(cur = cur.next);
    slow.next = slow.next.next;
    return first.next;
}

发表于 2021-04-25 00:51:06 回复(0)

JavaScript

别卷啦！

1.就不想用双指针就想用链表的反转查找和删除(时隔五个月回过头看想打死自己）

function removeNthFromEnd( head ,  n ) {
    // write code here
    //反转链表
    let prev = null
    let cur = head 
    const reverse = (prev,cur) =>{ 
    while(cur){
        let next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
        return prev
    }
    let newHead = reverse(prev,cur)
    //边界处理
    if(n==1) {
        return reverse(null, newHead.next)
    }
    //查询节点
    const findNodeIndex = (curSearchTmp,n) => {
        let pos = 1
        while(curSearchTmp &&pos !== n){
            curSearchTmp = curSearchTmp.next
            pos++
        }
        return curSearchTmp
    }
    let curSearch = findNodeIndex(newHead,n)
    //查找前一个节点
    let pre = findNodeIndex(newHead,n-1)
    //删除节点
    pre.next = curSearch.next
    let preNeed = null
    let curNeed = newHead
    //反转回来
    return reverse(preNeed,curNeed)
}

2.老老实实双指针快慢指针指向头部，快指针先走n-1，然后再同时走，快指针走到末尾的时候，慢指针指向倒数第k个节点

function removeNthFromEnd( head ,  n ) {
    // write code here
    let slow = head, fast = head
    while(n > 0){
        fast = fast.next
        n--
    }
    if(fast === null){
        slow = slow.next
        return slow 
    }
    while(fast.next){
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
    return head
}

编辑于 2021-06-15 23:00:04 回复(0)