題目

給定一系列正整數(shù)，請設(shè)計一個盡可能高效的算法，查找倒數(shù)第K個位置上的數(shù)字。

輸入格式:

輸入首先給出一個正整數(shù)K，隨后是若干非負(fù)整數(shù)，最后以一個負(fù)整數(shù)表示結(jié)尾（該負(fù)數(shù)不算在序列內(nèi)，不要處理）。

輸出格式:

輸出倒數(shù)第K個位置上的數(shù)據(jù)。如果這個位置不存在，輸出錯誤信息NULL。

輸入樣例:

4 1 2 3 4 5 6 7 8 9 0 -1

輸出樣例:

7

代碼

#include <stdio.h>
#include <stdlib.h>// 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)
struct ListNode {int val;struct ListNode* next;
};// 查找倒數(shù)第K個位置上的數(shù)字
int findKthFromEnd(struct ListNode* head, int k) {if (!head || k <= 0) return -1; // 如果鏈表為空或k小于等于0，返回-1表示錯誤struct ListNode* slow = head;struct ListNode* fast = head;// 快指針先移動k步for (int i = 0; i < k; ++i) {if (!fast) return -1; // 如果鏈表長度小于k，返回-1表示錯誤fast = fast->next;}// 同時移動慢指針和快指針，直到快指針到達(dá)鏈表尾部while (fast) {slow = slow->next;fast = fast->next;}return slow->val;
}int main() {int k;scanf("%d", &k);int num;struct ListNode* head = NULL;struct ListNode* tail = NULL;// 構(gòu)建鏈表while (scanf("%d", &num) && num >= 0) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = num;newNode->next = NULL;if (!head) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}int result = findKthFromEnd(head, k);if (result != -1) {printf("%d\n", result);} else {printf("NULL\n");}// 釋放鏈表內(nèi)存while (head) {struct ListNode* temp = head;head = head->next;free(temp);}return 0;
}

詳解

這個問題要求找出一個正整數(shù)序列中倒數(shù)第K個元素的值。為了解決這個問題，代碼使用了一個快慢指針的方法，并且用鏈表來存儲輸入的序列。下面是對這個算法和代碼的詳細(xì)解釋：

算法邏輯

1. 使用快慢指針:

   • 快指針 (fast) 和慢指針 (slow) 都從鏈表的頭結(jié)點(diǎn)開始。
   • 先讓快指針向前移動K步。這樣，快慢指針之間就保持了K個節(jié)點(diǎn)的距離。
   • 然后，同時移動快指針和慢指針，直到快指針到達(dá)鏈表的末尾。此時，慢指針?biāo)诘奈恢镁褪堑箶?shù)第K個節(jié)點(diǎn)。

2. 邊界條件處理:

   • 如果鏈表為空（head == NULL），或者K值不合理（k <= 0），函數(shù)直接返回-1，表示錯誤。
   • 如果鏈表長度小于K，也就是快指針在移動K步之前已經(jīng)到達(dá)了鏈表末尾，函數(shù)同樣返回-1。

代碼解釋

1. 鏈表節(jié)點(diǎn)定義:

   • struct ListNode 定義了鏈表的節(jié)點(diǎn)結(jié)構(gòu)，包括節(jié)點(diǎn)值 val 和指向下一個節(jié)點(diǎn)的指針 next。

2. 主函數(shù) main:

   • 讀取K值。
   • 通過循環(huán)讀取輸入的正整數(shù)，并構(gòu)建鏈表。遇到負(fù)數(shù)時停止讀取。
   • 調(diào)用 findKthFromEnd 函數(shù)來查找倒數(shù)第K個元素的值。

3. 查找函數(shù) findKthFromEnd:

   • 初始化快慢指針。
   • 讓快指針先移動K步。
   • 同時移動快慢指針，直到快指針到達(dá)末尾。
   • 返回慢指針?biāo)赶虻墓?jié)點(diǎn)的值。

4. 輸出結(jié)果:

   • 如果返回值不是-1，則輸出該值。
   • 如果返回值是-1，輸出"NULL"。

5. 釋放內(nèi)存:

   • 循環(huán)釋放鏈表的每個節(jié)點(diǎn)，避免內(nèi)存泄露。

這個算法的時間復(fù)雜度是O(n)，因為它最多遍歷鏈表兩次：一次用于構(gòu)建鏈表，一次用于找到倒數(shù)第K個元素。