【PTA刷题】求链式线性表的倒数第K项（代码+详解）

题目

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第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个元素的值。为了解决这个问题，代码使用了一个快慢指针的方法，并且用链表来存储输入的序列。下面是对这个算法和代码的详细解释：

算法逻辑

1. 使用快慢指针:

   • 快指针 (fast) 和慢指针 (slow) 都从链表的头结点开始。
   • 先让快指针向前移动K步。这样，快慢指针之间就保持了K个节点的距离。
   • 然后，同时移动快指针和慢指针，直到快指针到达链表的末尾。此时，慢指针所在的位置就是倒数第K个节点。

2. 边界条件处理:

   • 如果链表为空（head == NULL），或者K值不合理（k <= 0），函数直接返回-1，表示错误。
   • 如果链表长度小于K，也就是快指针在移动K步之前已经到达了链表末尾，函数同样返回-1。

代码解释

1. 链表节点定义:

   • struct ListNode 定义了链表的节点结构，包括节点值 val 和指向下一个节点的指针 next。

2. 主函数 main:

   • 读取K值。
   • 通过循环读取输入的正整数，并构建链表。遇到负数时停止读取。
   • 调用 findKthFromEnd 函数来查找倒数第K个元素的值。

3. 查找函数 findKthFromEnd:

   • 初始化快慢指针。
   • 让快指针先移动K步。
   • 同时移动快慢指针，直到快指针到达末尾。
   • 返回慢指针所指向的节点的值。

4. 输出结果:

   • 如果返回值不是-1，则输出该值。
   • 如果返回值是-1，输出"NULL"。

5. 释放内存:

   • 循环释放链表的每个节点，避免内存泄露。

这个算法的时间复杂度是O(n)，因为它最多遍历链表两次：一次用于构建链表，一次用于找到倒数第K个元素。