【題目8】查找單連結清單倒數第K個元素

解題思路：這個題目還是比較簡單的，用到一個非常簡單的方法就可以在0（n)時間内找到這個值。

具體的方案是一趟周遊，設立一個臨時指針pointer（初始值為第一個元素位置）和一個周遊的統

計個數（count = 0），周遊元素到達K個後，臨時指針指向第K+1個元素的位置，count清零，

重新計數，繼續周遊K個元素，直到達到連結清單尾。

這裡有兩種情況：

1.周遊完後,count剛好為K，pointer所指即使第K個元素

2. 如果count小于K，則pointer要往前移動（K-count+1)個位置。

補充：具體編碼實作後，才發現，上面的思路有一個很大的漏洞除了記錄臨時指針指向目前K個元素

的首位址外，還需要一個指針（Node* pre)記錄這個指針指向的前K個元素的首位址。

上面第2條，需要移動的指針，其實是pre, 這裡把原先錯誤的想法也記錄下來，以警醒自己，動手之

前一定要把問題想清楚，想明白。

參考代碼：

#include <stdio.h>

#include <stdlib.h>

struct Node

{

Node* next;

int value;

};

typedef Node* List;

Node* InsertNode(Node* head,int value)

{

if(head == NULL)

{

head = (Node*)malloc(sizeof(Node));

if(head == NULL)

printf("malloc failed.");

else

{

head->next = NULL;

head->value = value;

}

}

else

{

Node* cur = (Node*)malloc(sizeof(Node));

if(cur == NULL)

printf("malloc failed.");

else

{

cur->next = head;

head = cur;

cur->value = value;

}

}

return head;

}

Node* FreeLink(Node* head)

{

while(head->next)

{

Node* cur = head->next;

free(head);

head = cur;

}

return NULL;

}

void PrintLink(Node* head)

{

Node* p=head;

while(p->next)

{

printf("%d ",p->value);

p = p->next;

}

printf("%d/n",p->value);

}

int FindLastKthNode(List list, int K)

{

if(list == NULL || K < 0)

return -1;

List tmp = list;

List pre = tmp;

List p = list;

int count = 0;

int n = 0;

while(p)

{

if(p->next != NULL && count < K)

{

count++;

}

if(p->next != NULL && count == K)

{

pre = tmp;

tmp = p->next;

count = 0;

n++;

}

if(p->next == NULL && count < K)

{

if(n == 0)

printf("The length of the list is small than K.");

else

{

count++;

if(count == K)

n++;

else

{

int num = count;

while(num--)

pre = pre->next;

tmp = pre;

}

}

}

p = p->next;

}

if(n == 0)

return -1;

else

return tmp->value;

}

int main()

{

Node* link = NULL;

link = InsertNode(link, 9);

link = InsertNode(link, 8);

link = InsertNode(link, 7);

link = InsertNode(link, 6);

link = InsertNode(link, 5);

link = InsertNode(link, 4);

link = InsertNode(link, 3);

link = InsertNode(link, 2);

link = InsertNode(link, 1);

PrintLink(link);

printf("%d/n",FindLastKthNode(link,7));

FreeLink(link);

return 0;

}

 2009年9月25日：其實這道題還有一個更加簡單的解法，設定兩個指針，一個

指針指向連結清單頭，另一個指向前一指針間隔為K的位置。

int FindLastKthNode2(List list, int K)

{

List p1 = list;

List p2 = list;

int i = K;

while(i > 0)

{

p2 = p2->next;

--i;

}

while(p2 != NULL)

{

p1 = p1->next;

p2 = p2->next;

}

return p1->value;

}

後記：不自己動手試一下，很難發現其中的問題，寫了個驅動程式

跑一下，發現了很多原來沒有注意到的問題，調試花了不少時間。

現在這個程式可以正确運作了，有興趣的同學可以自己寫個驅動程

序跑一下試試看。