首页 > 代码库 > 数据结构——求单向链表的倒数第K个节点
数据结构——求单向链表的倒数第K个节点
首先，对于链表来说，我们不能像数组一样直接访问，所以我们想到要求倒数第K个节点首先要知道最后一个节点。
然后从最后一个节点往前数K个。
最后得到想要的值。
但是这是不对的，为什么呢？因为题目给出的是单向链表，只能从前往后找。
所以我们需要换一种思路。
定两个指针。
都从链表的头开始走，一个先走一个后走，先走的比后走的快k步。
然后两个人之后每次都走一步。
当先走的走到终点的时候。
那么后走的所在的位置就是倒数第K个节点的位置了。
下面是代码，这次使用STL库中的list完成。
/***单向链表求倒数的第K个节点的值 **/ #include <cstdio>#include <cstdlib> #include <iostream>#include <algorithm>#include <list>using namespace std;//定义一个链表 list<int> linklist;//打印链表中的元素 void print_list(){ list<int>::iterator linklistIterator; for(linklistIterator=linklist.begin(); linklistIterator!=linklist.end(); linklistIterator++) cout<<*linklistIterator<<" "; cout<<endl;}int main() { //创建链表中的元素 for(int i=1; i<=10; i++) linklist.push_back(i); print_list(); //要求寻找到，倒数第3个元素。 int k=3; list<int>::iterator iterator_A=linklist.begin(); list<int>::iterator iterator_B=linklist.begin(); for(int i=1; i<=k; i++) iterator_A++; while(iterator_A != linklist.end()) { iterator_A++; iterator_B++; } cout<<"倒数第三个元素是："<<*iterator_B<<endl; return 0;}
数据结构——求单向链表的倒数第K个节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。