我理解的剑指Offer--------链表中倒数第k个结点
- 题目描述：
-
输入一个链表，输出该链表中倒数第k个结点。
(hint: 请务必使用链表。)
- 输入：
-
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000)：n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。
输入的第二行包括n个数t(1<=t<=1000000)：代表链表中的元素。
- 输出：
-
对应每个测试案例，
若有结果，输出相应的查找结果。否则，输出NULL。
- 样例输入：
-
5 2 1 2 3 4 5 1 0 5
- 样例输出：
-
4 NULL
我的理解：
就是用一把刻度为k的尺子量长度为n的木棍，量好k之后，把尺子平移，到达棍子的尽头。这样尺子的开头就是倒数第k个刻度。
【解析】
【代码】
- /*********************************
- *日期：2013-11-20
- *作者：SJF0115
- *题号:题目1517：链表中倒数第k个结点
- *来源：http://ac.jobdu.com/problem.php?pid=1517
- *结果：AC
- *来源：剑指Offer
- *总结：
- **********************************/
- #include<iostream>
- #include<stdio.h>
- #include<malloc.h>
- #include<string.h>
- usingnamespacestd;
- typedefstructListNode{
- intvalue;
- structListNode*next;
- }ListNode;
- intFindKthToTail(ListNode*head,intk){
- //容错处理
- if(head==NULL||k<=0){
- returnNULL;
- }
- else{
- ListNode*p,*pre;
- //带头节点的链表
- pre=p=head->next;
- //第一个指针向前走k-1步，第二个指针保持不变
- for(inti=0;i<k-1;i++){
- p=p->next;
- }
- //两个指针同时向前遍历
- while(p->next!=NULL){
- pre=pre->next;
- p=p->next;
- }
- returnpre->value;
- }
- }
- intmain()
- {
- inti,n,k;
- while(scanf("%d%d",&n,&k)!=EOF){
- ListNode*head,*p,*pre;
- head=(ListNode*)malloc(sizeof(ListNode));
- head->next=NULL;
- pre=head;
- for(i=0;i<n;i++){
- p=(ListNode*)malloc(sizeof(ListNode));
- scanf("%d",&p->value);
- p->next=NULL;
- pre->next=p;
- pre=p;
- }
- //全部输出
- if(n<k){
- printf("NULL\n");
- }
- else{
- //倒数K个
- intnum=FindKthToTail(head,k);
- if(num==NULL){
- printf("NULL\n");
- }
- else{
- printf("%d\n",num);
- }
- }
- }
- return0;
- }