剑指offer-面试题15.链表中倒数第k个结点
2024-10-06 23:57:57
题目:输入一个链表,输出该链表的倒数第K个结点。为了符合大多数人的习惯,本题
从1开始计数,即链表的尾结点是倒数第1个节点。例如有一个链表有6个节点,从
头节点开始他们的值依次是1,2,3,4,5,6.这个链表的倒数第三个节点是值为4的节点。
这个题目常规情况下我们都是考虑先从链表的头遍历到链表的尾,然后后退k步取倒数第
k个节点的值。
然而我们也可以这样考虑先遍历一遍链表计算出链表的长度N,要取出倒数的第k个,其实就是
从链表头走N-k+1步便到了倒数第k个节点,但是这种方式似乎并没有什么改进。
然而我们可以举这样一个例子3->2->4->5->9->6我们要取出倒数第三个元素即值为5的元素
我们可以设置两个指针ptr1和ptr2这两个指针开始都指向3,然后ptr1向后移动k-1步即移动到第四
个元素的位置。这时候ptr1和ptr2再同时移动知道ptr1指向最后一个元素,这时候ptr正好指向5
两个指向之间相差正好k-1个元素。
代码实现如下:
#include <iostream>
#include <stack>
using namespace std; struct ListNode
{
int data;
struct ListNode *next;
}; struct ListNode* CreateList()
{
struct ListNode* Head,*p;
Head=(struct ListNode*)malloc(sizeof(ListNode));
Head->data=;
Head->next=NULL;
p=Head; cout<<"Create List....(0-exit!)"<<endl;
while(true)
{
int Data;
cin>>Data;
if(Data!=)
{
struct ListNode* NewNode;
NewNode=(struct ListNode*)malloc(sizeof(ListNode));
NewNode->data=Data;
NewNode->next=NULL;
p->next=NewNode;
p=p->next;
}
else
{
break;
}
} return Head->next;
} void PrintList(struct ListNode* Head)
{
cout<<"The List is: "; struct ListNode *p;
p=Head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
} ListNode* FindKthToTail(ListNode* pListHead,unsigned int k)
{
ListNode *ptr1,*ptr2;
ptr1=pListHead;
ptr2=pListHead; if(pListHead==NULL||k==0)
return NULL; int count=;
/* while(count<=(k-))
{
ptr1=ptr1->next;
count++;
}*/ //未考虑到当k大于链表本身的长度
改:
while(count<=(k-1))
{
if(ptr1->next==NULL)
{
return NULL;
}
else
{
ptr1=ptr1->next;
count++;
}
} while(ptr1!=NULL)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
} return ptr2;
} int main()
{
ListNode *Head;
Head=CreateList();
PrintList(Head);
if(FindKthToTail(Head,))
{
cout<<"Last K value in List is: "<<FindKthToTail(Head,)->data<<endl;
}
return ;
}
运行截图:
最新文章
- PRML读书笔记——3 Linear Models for Regression
- 仿苹果导航菜单js问题
- 应用HTK搭建语音拨号系统2:创建单音素HMM模型
- 2014 网选 5014 Number Sequence(异或)
- android自定义控件之滚动广告条
- 学习iOS开发的前言
- Android中Socket通信之TCP与UDP传输原理
- [Swift]LeetCode818. 赛车 | Race Car
- idea在Terminal中使用maven指令
- video 自动循环播放
- leetcode1035
- pandas数据的分组与分列
- linux命令之kill篇
- Hbase记录-Hbase shell使用
- AngularJS之登录显示用户名
- 13机器学习实战之PCA(2)
- CSS分列等高
- Centos7搭建pptp一键安装脚本
- OpenStack计费项目Cloudkitty系列详解(一)
- ES5和ES6中的继承
热门文章
- 【PAT L2-001】最短路计数
- hdu 4504 威威猫系列故事——篮球梦_简单dp
- linux驱动面试题2
- Objective-C中NSString和NSMutableString的基本用法
- TextView总结
- jQuery插件Jeditable的使用(Struts2处理)
- android jni (5)——Field &; Method -->; Accessing Mehtod
- spring + jdbc + extjs configuration
- VML :Vector Markup Language
- 未能加载文件或程序集“System.Web.Helpers, Version=2.0.0.0(转)