首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点
  • 热度指数：420444 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。


数据范围：，，
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例1

输入

{1,2,3,4,5},2

输出

{4,5}

说明

返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2

输入

{2},8

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Go
愿offer多多的咸鱼很开心头像 愿offer多多的咸鱼很开心
这就学快慢指针 
var w = 1
var l  *ListNode
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    if pHead == nil {
        return pHead
    }

    if pHead.Next != nil {
        FindKthToTail(pHead.Next, k)
    }

    if w == k {
        if l == nil {
            l = pHead
        }
    }else {
        w +=1
    }
    fmt.Print(w)
    return l

}


发表于 2023-08-17 00:45:33 回复(0)
Go
姚文帆头像 姚文帆
解法一：快慢指针 
func FindKthToTail(pHead *ListNode, k int) *ListNode {
	// write code here
	//快慢指针
	p1 := pHead
	p2 := pHead
	for i := 0; i < k; i++ {
        if p1==nil {
            return nil
        }
		p1 = p1.Next
	}
	for p1 != nil {
		p2 = p2.Next
		p1 = p1.Next
	}
	return p2
}
解法二：先找出链表长度 
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    n := 0
    flag := pHead
    for pHead!=nil {
        n++
        pHead=pHead.Next
    }
    if n<k {
        return nil
    }
    for i:=0;i<n-k;i++ {
        flag= flag.Next
    }
    return flag
}



发表于 2022-06-23 02:56:54 回复(0)
Go
风轻云淡.头像 风轻云淡. 
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    fast,slow:=pHead,pHead
    for i:=0;i<k;i++{
        if fast==nil{
            return nil
        }
        fast=fast.Next
    }
    for fast!=nil{
        fast=fast.Next
        slow=slow.Next
    }
    return slow
}

发表于 2022-04-19 14:51:42 回复(0)
Go
admxt头像 admxt
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    len:=0
    current:=pHead
    for current!=nil{
        len++
        current=current.Next
    }
    p:=len-k+1
    if p<=0{
       return nil
    }
    i:=1
    for i<p{
        i++
        pHead=pHead.Next
    }
    return pHead
}
发表于 2022-02-25 15:11:08 回复(1)
Go
codewind头像 codewind 
package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
*/
func FindKthToTail( p *ListNode ,  k int ) *ListNode {
    // write code here
    if p==nil || p.Next ==nil { return p }
    var slow,fast *ListNode
    slow = p 
    fast = p 
    
    for i:=0;i<k;i++ {
        if fast == nil { return nil }
        fast = fast.Next
    }
    
    //fast != nil 
    for fast !=nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
    
    
    
    
    
}

发表于 2022-01-13 21:18:50 回复(0)
Go
正版沨头像 正版沨
【Golang】快慢指针解法 
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // 临界情况判断
    if pHead == nil || k < 1 {
        return nil
    }
    fast, slow := pHead, pHead
    for i := 0; i < k; i++ {
        // 注意k大于链表长度的情况
        if fast == nil { return nil }
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}


发表于 2021-07-24 19:48:49 回复(0)
提交观点

问题信息

链表
上传者：灵溪吴彦祖
难度：
6条回答 8967浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链表中倒数最后k个结点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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