首页 > 试题广场 >

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

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

热度指数：11175 时间限制：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

输入

输出

备注:

请自觉实现一个链表，将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 展开全文

牛客题解官

发表于 2020-06-05 17:21:03

题解题目难度：简单知识点：查找、链表解题思路：这是一道考察链表知识点的题，要求输出倒数第k个节点的值，因为此链表结构是顺着保存数据的，所以指针无法访问倒数的值。解题关键在使用两个距离相差k的指针进行数据访问，一旦第一个指针已经到最后的节点时，此时第二个指针所在的位置刚好是倒数第k个节点。题解展开全文