我要招人

去企业版

首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点

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

输入一个长度为 n 的链表，设链表中的元素的值为 a_i ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围： $0 \leq n \leq 10^5$ ， $0 \leq a_i \leq 10^9$ ， $0 \leq k \leq 10^9$

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

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入

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

输出

{4,5}

说明

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

示例2

输入

{2},8

输出

{}

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

算法知识视频讲解

Maokt

发表于 2021-06-23 16:27:34

精华题解算法思想一：快慢指针解题思路：第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可图解：代码展示： class Solution: &nb 展开全文

牛客题解官

发表于 2022-04-22 11:28:29

精华题解题目的主要信息：一个长度为nnn的链表，返回原链表中从倒数第k个节点至尾节点的全部节点如果该链表长度小于k，请返回一个长度为 0 的链表举一反三：学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM6.判断链表中是否有环 BM7.链表中环的入口节展开全文

大菠萝侦探

发表于 2021-06-22 20:59:02

精华题解描述输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。数组法把每个节点装进数组中，访问倒数第 k 个元素。 class Solution { public: ListNode* FindKthToT 展开全文

开车的阿Q

发表于 2021-06-21 22:04:23

精华题解描述这是一篇面对初级coder的题解。知识点：链表栈难度：一星题解题目：输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。考察链表的基础知识方法一：栈展开全文

2019113913

发表于 2021-07-15 12:43:56

精华题解题意思路：输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。方法一:双指针定义两个指针，i和j指向链表的头结点。 i指针先走k步，如果链表的长度也等于k的话，快指针走k步正好会走到空。如果在走第k步之前链表展开全文

咪咪虾条001

发表于 2021-02-26 19:22:56

在链表中：倒数的+顺数的长度等于链表总长度，所以可以设置两个指针，一个先走K步，剩下的到链表的末尾要走的步数就是倒数第k个节点，需要从头开始走的步数 public ListNode FindKthToTail (ListNode pHead, int k) { // write co 展开全文

数据结构和算法

发表于 2021-04-02 16:14:45

1，双指针求解这题要求链表的倒数第k个节点，最简单的方式就是使用两个指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可。注意，如果第一个指针还没走k步的时候链表就为空了，我们直接返回null即可。 publ 展开全文

AcKei

发表于 2021-03-07 22:44:24

这道题用双指针即可，倒数第k个，其实就是正数n-k+1个。先让快指针走k步，然后slow从head出发，跟fast一步一步走，当fast走到尾（空节点）时，slow的位置正在n-k+1。但是还得注意一些极值情况，比如链表为空或者k大于链表节点时。上代码： public ListNode Fi 展开全文

汤姆和佩奇

发表于 2021-09-18 10:30:45

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { // pu 展开全文

不是江小白

发表于 2021-08-05 13:39:48

1. 解题思路一般链表题，我们都可以考虑双指针的解题思路，此题同样可以。首先注意题目描述里这句👇“如果该链表长度小于k，请返回一个长度为 0 的链表。” 意味着如果链表为空，那么直接返回None即可。然后结合示例1，继续分析：首先创建两个指针，指向头部节点：然后根据k值，移动first指展开全文

菜鸡孙连城

发表于 2022-03-15 20:16:37

原来这道题也可以快慢指针，惊呆了注意：1.快指针走k步的时候注意判断fast是否为null function FindKthToTail( pHead , k ) { let fast = pHead, slow = pHead; for(let i=0;i<k;i++) 展开全文

王清楚

发表于 2021-03-23 17:49:00

解法：定义两个指针，fast，slow指向链表的头结点。 fast指针先走k步，走的时候要注意判断一下链表的长度是否大于等于k。如果链表的长度也等于k的话，快指针走k步正好会走到空。如果在走第k步之前链表就指向空的话，说明链表长度小于k，直接返回空。然后fast指针和slow指针一起走。当fa 展开全文

封心忘忧

发表于 2022-08-04 11:37:03

struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) { struct ListNode* 展开全文

牛客566659818号

发表于 2022-08-03 10:30:03

此题思路快慢指针，先用快指针走k步，如果k的大小没有超过链表大小，则快慢指针同时移动，这样两者始终保持k距离，当快指向空时，返回慢指针即为倒数的k个结点 struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) { & 展开全文

liuzhen007

发表于 2021-03-06 10:40:59

题目描述：输入一个链表，输出该链表中倒数第k个结点。题目链接：http://www.nowcoder.com/questionTerminal/886370fe658f41b498d40fb34ae76ff9 按部就班的解法，这就双百了？不过展开全文

问题信息

链表

上传者：灵溪吴彦祖

难度：

432条回答 865收藏 8963浏览

通过挑战的用户

查看代码

牛客47096...

2023-03-09 21:38:33
cdjb

2023-02-07 00:21:31
Chensp

2023-01-31 15:47:21
Zhaaaaaaa

2023-01-19 21:46:58
Y/B＆P!

2023-01-07 10:56:20

链表中倒数最后k个结点

输入

输出

说明

输入

输出

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

问题信息

热门推荐

通过挑战的用户

相关试题