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

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

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

算法知识视频讲解

查看答案及解析

SoEasy2022

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

for next.Next != nil{
pre, cur, next = cur, cur.Next, next.Next
}
pre.Next = cur.Next
return head
}

发表于 2022-03-11 11:52:37 回复(0)

admxt

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

发表于 2022-02-25 16:14:28 回复(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)