首页 > 试题广场 >

找出单向链表中的一个节点，该节点到尾指针的距离为K

[编程题]找出单向链表中的一个节点，该节点到尾指针的距离为K
  • 热度指数：11247 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
找出单向链表中的一个节点，该节点到尾指针的距离为K。链表的倒数第0个结点为链表的尾指针。要求时间复杂度为O(n)。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
链表节点的值初始化为1，2，3，4，5，6，7。

输入描述:
该节点到尾指针的距离K


输出描述:
返回该单向链表的倒数第K个节点，输出节点的值
示例1

输入

2

输出

6

备注:
请自觉实现一个链表，将1到7依次加入链表，然后再寻找倒数第K个节点。要求加节点与找节点的操作复杂度均为O(n)。
算法知识视频讲解
开通博客
头像 牛客551801357号
发表于 2023-04-18 15:26:11
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { class ListNode{ public int key; public ListNo 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-05 17:21:03
题解 题目难度：简单 知识点：查找、链表 解题思路：这是一道考察链表知识点的题，要求输出倒数第k个节点的值，因为此链表结构是顺着保存数据的，所以指针无法访问倒数的值。解题关键在使用两个距离相差k的指针进行数据访问，一旦第一个指针已经到最后的节点时，此时第二个指针所在的位置刚好是倒数第k个节点。 题解 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 张CM
发表于 2024-06-03 11:17:35
#include <iostream> using namespace std; struct ListNode { int m_nKey; ListNode* m_pNext; }; ListNode *head,*r,*p,*d; int pos; int main() { 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 swaaaay
发表于 2021-11-23 15:46:32
列表转链表，再双指针 class node: def __init__(self, data): self.val = data self.next = None class Solution: def __init__(self): 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 数组 小米集团 链表 测试开发工程师 测试工程师 2019 Java工程师
来自：小米2019秋招测试开...
上传者：小小
难度：
55条回答 11470浏览

热门推荐

通过挑战的用户

查看代码

相关试题

找出单向链表中的一个节点，该节点到尾指针的距离为K

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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