返回倒數(shù)第 k 個節(jié)點

實例要求

• 1、實現(xiàn)一種算法，找出單向鏈表中倒數(shù)第 k 個節(jié)點；
• 2、返回該節(jié)點的值；

示例：輸入： 1->2->3->4->5 和 k = 2
輸出： 4
說明：給定的 k 保證是有效的。

實例分析

• 1、定義快慢指針；
• 2、快指針先移動k步、鏈表長度小于k，返回特殊值；
• 3、快指針和慢指針同時移動，直到快指針到達鏈表末尾；
• 4、慢指針指向倒數(shù)第k個節(jié)點；

示例代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){if (head == NULL || k <= 0) {return -1; // 返回一個特殊值表示無效輸入}struct ListNode* fast = head;struct ListNode* slow = head;// 快指針先移動k步for (int i = 0; i < k; i++) {if (fast == NULL) {return -1; // 鏈表長度小于k，返回特殊值}fast = fast->next;}// 快指針和慢指針同時移動，直到快指針到達鏈表末尾while (fast != NULL) {fast = fast->next;slow = slow->next;}// 慢指針指向倒數(shù)第k個節(jié)點return slow->val;}

代碼解釋

• 1、int kthToLast(struct ListNode* head, int k): 這個函數(shù)接收一個指向鏈表頭部的指針 head 和一個整數(shù) k，表示要找的倒數(shù)第 k 個節(jié)點。函數(shù)返回倒數(shù)第 k 個節(jié)點的值；
• 2、如果輸入的鏈表頭指針為空 head == NULL 或者 k 的值小于等于 0 k <= 0，則返回一個特殊值 -1，表示無效輸入；
• 3、接著，定義兩個指針 fast 和 slow，初始都指向鏈表的頭部 head；
• 4、使用快慢指針的技巧，快指針 fast 先向前移動 k 步；
• 5、如果鏈表的長度小于 k，即快指針已經(jīng)到達鏈表末尾時仍然為 NULL，則返回特殊值 -1，表示無效輸入；
• 6、接著，快指針 fast 和慢指針 slow 同時向前移動，直到快指針 fast 到達鏈表末尾（即 fast == NULL）；
• 7、此時慢指針 slow 指向的節(jié)點就是倒數(shù)第 k 個節(jié)點，返回其值 slow->val。

運行結(jié)果