【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个元素。