题目
给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。
输入格式:
输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。
输出格式:
输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息
NULL。输入样例:
4 1 2 3 4 5 6 7 8 9 0 -1
输出样例:
7
代码
#include <stdio.h> #include <stdlib.h> // 定义链表节点结构 struct ListNode { int val; struct ListNode* next; }; // 查找倒数第K个位置上的数字 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; } // 同时移动慢指针和快指针，直到快指针到达链表尾部 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; // 构建链表 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"); } // 释放链表内存 while (head) { struct ListNode* temp = head; head = head->next; free(temp); } return 0; }
详解
这个问题要求找出一个正整数序列中倒数第K个元素的值。为了解决这个问题，代码使用了一个快慢指针的方法，并且用链表来存储输入的序列。下面是对这个算法和代码的详细解释：
算法逻辑
- 使用快慢指针:
- 快指针 (
fast) 和慢指针 (slow) 都从链表的头结点开始。 - 先让快指针向前移动K步。这样，快慢指针之间就保持了K个节点的距离。
- 然后，同时移动快指针和慢指针，直到快指针到达链表的末尾。此时，慢指针所在的位置就是倒数第K个节点。
- 边界条件处理:
- 如果链表为空（
head == NULL），或者K值不合理（k <= 0），函数直接返回-1，表示错误。 - 如果链表长度小于K，也就是快指针在移动K步之前已经到达了链表末尾，函数同样返回-1。
代码解释
- 链表节点定义:
struct ListNode定义了链表的节点结构，包括节点值val和指向下一个节点的指针next。
- 主函数
main:
- 读取K值。
- 通过循环读取输入的正整数，并构建链表。遇到负数时停止读取。
- 调用
findKthFromEnd函数来查找倒数第K个元素的值。
- 查找函数
findKthFromEnd:
- 初始化快慢指针。
- 让快指针先移动K步。
- 同时移动快慢指针，直到快指针到达末尾。
- 返回慢指针所指向的节点的值。
- 输出结果:
- 如果返回值不是-1，则输出该值。
- 如果返回值是-1，输出"NULL"。
- 释放内存:
- 循环释放链表的每个节点，避免内存泄露。
这个算法的时间复杂度是O(n)，因为它最多遍历链表两次：一次用于构建链表，一次用于找到倒数第K个元素。
