C语言面试题之返回倒数第 k 个节点

返回倒数第 k 个节点

实例要求

• 1、实现一种算法，找出单向链表中倒数第 k 个节点；
• 2、返回该节点的值；

示例：输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：给定的 k 保证是有效的。

实例分析

• 1、定义快慢指针；
• 2、快指针先移动k步、链表长度小于k，返回特殊值；
• 3、快指针和慢指针同时移动，直到快指针到达链表末尾；
• 4、慢指针指向倒数第k个节点；

示例代码

/*** 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;}// 慢指针指向倒数第k个节点return slow->val;}

代码解释

• 1、int kthToLast(struct ListNode* head, int k): 这个函数接收一个指向链表头部的指针 head 和一个整数 k，表示要找的倒数第 k 个节点。函数返回倒数第 k 个节点的值；
• 2、如果输入的链表头指针为空 head == NULL 或者 k 的值小于等于 0 k <= 0，则返回一个特殊值 -1，表示无效输入；
• 3、接着，定义两个指针 fast 和 slow，初始都指向链表的头部 head；
• 4、使用快慢指针的技巧，快指针 fast 先向前移动 k 步；
• 5、如果链表的长度小于 k，即快指针已经到达链表末尾时仍然为 NULL，则返回特殊值 -1，表示无效输入；
• 6、接着，快指针 fast 和慢指针 slow 同时向前移动，直到快指针 fast 到达链表末尾（即 fast == NULL）；
• 7、此时慢指针 slow 指向的节点就是倒数第 k 个节点，返回其值 slow->val。

运行结果