题目
输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
思路一
因为是单向链表,只有从前往后的指针而没有从后往前的指针。因此我们不能倒序遍历链表,只能正序遍历。假设整个链表有n个结点,那么倒数第k个结点是从头结点开始的第n-k-1个结点(从0开始计数)。我们只需要得到链表中结点的个数n,那我们只要从头结点开始往后走n-k-1步就可以了。
因此这种方法需要遍历链表两次。第一次得到链表中结点个数n,第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。时间复杂度为O(n)。
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindKthTailNode(ListNode* head,int k) {
if(head == nullptr || k < 0){
return nullptr;
}
int count = 0;
ListNode *p = head;
while(p){
p = p->next;
++count;
}
if(count < k){
return nullptr;
}
int pos = count - k;
p = head;
for(int i = 0;i < pos;++i){
p = p->next;
}
return p;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}
ListNode *result = s.FindKthTailNode(head,3);
if(result == nullptr){
cout<<"nullptr"<<endl;
}
else{
cout<<result->val<<endl;
}
return 0;
}
思路二
上面那种思路需要两次遍历,如何才能只需一次遍历呢?
如果我们在遍历时维持两个指针,第一个指针从链表的头指针开始遍历,在第k-1步之前,第二个指针保持不动, k-1 步开始,第二个指针也开始从链表的头指针开始遍历,两个指针齐头并进。由于两个指针的距离保持在k-1;当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第
K个节点。
代码二
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindKthTailNode(ListNode* head,int k) {
if(head == nullptr || k < 0){
return nullptr;
}
ListNode *p = head,*q = head;
int index = 1;
while(index < k && p != nullptr){
p = p->next;
++index;
}
if(p == nullptr){
return nullptr;
}
while(p->next){
p = p->next;
q = q->next;
}
return q;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}
ListNode *result = s.FindKthTailNode(head,8);
if(result == nullptr){
cout<<"nullptr"<<endl;
}
else{
cout<<result->val<<endl;
}
return 0;
}
拓展
输入一个单向链表。如果该链表的结点数为奇数,输出中间的结点;如果链表结点数为偶数,输出中间两个结点前面的一个节点。
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode* FindMidNode(ListNode* head) {
if(head == nullptr){
return nullptr;
}
ListNode *slow = head,*fast = head;
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
int main(){
Solution s;
ListNode *head = new ListNode(1);
ListNode *node;
for(int i = 8;i >= 2;--i){
node = new ListNode(i);
node->next = head->next;
head->next = node;
}
ListNode *result = s.FindMidNode(head);
if(result == nullptr){
cout<<"nullptr"<<endl;
}
else{
cout<<result->val<<endl;
}
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
查找链表中倒数第K个节点,源代码验证通过,两种查找方法。
剑指 Offer 22. 链表中倒数第k个节点输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点
剑指 Offer 22. 链表中倒数第k个节点难度:简单题目:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点
此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到第 N - K 个节点处,该位置就是倒数第 K 个节点。public List
此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到第 N - K 个节点处,该位置就是倒数第 K 个节点。public List
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
剑指 Offer 22. 链表中倒数第k个节点难度:简单输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数
解答一遍历链表两次,第一次获得长度,第二个走(n-k+1)步ListNode* findK(ListNode* head,unsigned int k)解答二双
NULL 博文链接:https://128kj.iteye.com/blog/1748487
删除链表中倒数第N个结点后,返回结果链表的首结点
链表功能的一个扩展延伸,查找倒数第K个元素,是某年考研题
java基础面试题链表中倒数第K个点
删除链表的倒数第N个节点、面试题02.07.链表相交和142.环形链表II。记录了清晰的文字题解+图示以及Java参考代码。 适合人群:链表算法感兴趣的程序员或学生,想要打好数据结构与算法基础的人。 能学到什么:掌握链表...
题:输入一个链表,输出该链表中倒数第k个结点。 解题思路一:为了实现只遍历链表一次就能找到倒数第k个节点,我们可以定义两个指针。让第一个指针先向前走k-1步,第二个指针保持不动;从第k步开始,第二个指针也...
题目输入一个链表,输出该链表中倒数第k个结点思路将输入链表赋给两个链表;然后和另外一个链表一起走到链表尾,另外一个链表即在倒数第k个结点。if head ==
java面试 java面试_leetcode面试题解之第19题删除链表的倒数第N个结点
python_leetcode面试题解之第19题删除链表的倒数第N个结点
由第三方作者花费大量时间收集并整理散落在茫茫网络中的面经,并从中精选出若干具有代表性的技术类的面试题展开讨论,希望能给读者带来一些启发 例如; 把二元查找树转变成排序的双向链表 设计包含min函数的栈 把...
我们在找嵌入式方面的工作时,让我们头疼的恐怕就是面试题了,因为我们摸不到企业的命题规律,也不知道该怎样去准备,今天将各大企业的面试题进行汇总,分享给大家,希望可以帮到各位小伙伴。加油哦!
输入一个链表,输出该链表中倒数第k个结点 解题思路 本题的思路和之前看矩形那一题有相似之处,就是我们优先考虑边界情况,比如本题,我们需要查找链表中的倒数第K个节点,那么想象此时身处链表最后的位置,我想要...