【剑指offer 面试题15】链表中倒数第K个结点
2024-09-24 09:40:41
思路:
定义两个指针同时指向head,第一个指针先走K-1步,随后二个指针同时移动,当第一个指针到末尾处时,第二个指针所指向的即为倒数第K个结点。
#include <iostream>
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int v = ):val(v), next(NULL){}
}; ListNode *findLastKthnumber(ListNode **pListHead, unsigned int k)
{
if(*pListHead == NULL || k == )
return NULL; ListNode *pFirst = *pListHead;
ListNode *pSecond = *pListHead; for(int i = ; i < k - ; i++)
{
pFirst = pFirst->next;
if(pFirst == NULL)
return NULL;
} while(pFirst->next != NULL)
{
pFirst = pFirst->next;
pSecond = pSecond->next;
} return pSecond;
} int main()
{
ListNode *first = new ListNode();
ListNode *head = first; ListNode *second = new ListNode();
first->next = second;
first = first->next; ListNode *third = new ListNode();
first->next = third;
first = first->next; cout<<"初始链表: ";
ListNode *print = head;
while(print != NULL)
{
cout<<print->val<<" ";
print = print->next;
}
cout<<endl<<endl; cout<<"倒数第零个结点: ";
ListNode *res = findLastKthnumber(&head, );
if(res != NULL)
cout<<res->val<<endl;
else
cerr<<"error!"<<endl; cout<<"倒数第一个结点: ";
res = findLastKthnumber(&head, );
if(res != NULL)
cout<<res->val<<endl;
else
cerr<<"error!"<<endl; cout<<"倒数第二个结点: ";
res = findLastKthnumber(&head, );
if(res != NULL)
cout<<res->val<<endl;
else
cerr<<"error!"<<endl; cout<<"倒数第三个结点: ";
res = findLastKthnumber(&head, );
if(res != NULL)
cout<<res->val<<endl;
else
cerr<<"error!"<<endl; cout<<"倒数第四个结点: ";
res = findLastKthnumber(&head, );
if(res != NULL)
cout<<res->val<<endl;
else
cerr<<"error!"<<endl;
}
测试结果:
初始链表: 倒数第零个结点: error!
倒数第一个结点:
倒数第二个结点:
倒数第三个结点:
倒数第四个结点: error!
最新文章
- <;<;<; html编码中js和html编码不一致导致乱码
- sqlserverdriver配置方法 jdbc连接sqlserver
- ZIP打包解包
- angularjs笔记(一)
- android 入门-工序
- JPA(4)表表关联关系
- 关于Action<;T>; 、Func<;T>;、EventHandler<;T>;、event、delegate
- oracle split
- intent.addFlags(Intent.FLAG_ACTIVITY_NO_HISTORY);
- Android学习笔记(一)开发环境搭建
- STL之Vector(不定长数组)
- iOS基础 - 瀑布流
- IDL 字符串
- 模式识别笔记4-集成学习之AdaBoost
- VS2008中捕获内存泄露(转)
- Atitit phpstorm配置attilax总结
- 细细探究MySQL Group Replicaiton — 配置维护故障处理全集(转)
- Swift 常量、变量、条件判断
- node中非常重要的process对象,Child Process模块
- poj3252Round Numbers【组合数】【数位dp】
热门文章
- cojs 香蕉 解题报告
- 获取其它进程窗口中的状态栏信息(FindWindowEx GetWindowThreadProcessId OpenProcess SendMessage轮番轰炸)
- servlet会话技术:Session
- 修改linux命令行提示符路径显示
- spring boot 1.4默认使用 hibernate validator
- python小问题记录:
- ios7 webapp touch bug
- C# WinForm窗体 控件Control 的 Invalidate、Update、Refresh的区别
- 分批次获取git for windows的源代码
- find-all-duplicates-in-an-array(典型的数组中的重复数,不错,我做出来了,可是发现别人有更好的做法)