794
劍指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
【代碼】
/*********************************
* 日期：2013-11-20
* 作者：SJF0115
* 題號: 題目1517：鏈表中倒數第k個結點
* 來源：https://ac.jobdu.com/problem.php?pid=1517
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;
typedef struct ListNode{
int value;
struct ListNode *next;
}ListNode;
int FindKthToTail(ListNode*head,int k){
//容錯處理
if(head == NULL || k <= 0){
return NULL;
}
else{
ListNode *p,*pre;
//帶頭節點的鏈表
pre = p = head->next;
//第一個指針向前走k-1步，第二個指針保持不變
for(int i = 0;i < k-1;i++){
p = p->next;
}
//兩個指針同時向前遍曆
while(p->next != NULL){
pre = pre->next;
p = p->next;
}
return pre->value;
}
}
int main()
{
int i,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個
int num = FindKthToTail(head,k);
if(num == NULL){
printf("NULL\n");
}
else{
printf("%d\n",num);
}
}
}
return 0;
}
最後更新：2017-04-03 14:54:23