---

算法题

思路

因为是求倒数第k个元素，所以可以用一个指针先跑k个结点，然后和另一个指针同时跑，直到先跑的指针为NULL为止，两个指针都初始化为第一个有效结点。

typedef struct Node{
	int data;
	struct Node *link;
}Node;

Node* get_back_k(Node *list, int k) {
    // 1. 检查链表是否为空 (只包含头结点)
    // 假设 list 是头结点，list->link 指向第一个数据结点
    if (list == NULL || list->link == NULL) { // 链表为空或只有头结点
        return NULL; // 空链表没有倒数第k个元素
    }
    
    // 确保 k 是有效的正整数
    if (k <= 0) {
        return NULL; // k 必须是正整数
    }

    Node* prior = list->link; // prior 从第一个数据结点开始
    Node* rear = list->link;  // rear 也从第一个数据结点开始

    // 2. prior 指针先行 k 步
    for (int i = 0; i < k; i++) {
        if (prior == NULL) { // 如果 prior 在走了 k 步之前就到达了链表末尾
            return NULL; // 说明 k 太大，链表没有 k 个元素
        }
        prior = prior->link;
    }

    // 3. prior 和 rear 同时移动，直到 prior 到达链表末尾
    // 当 prior 到达 NULL 时，rear 就会指向倒数第 k 个元素
    while (prior != NULL) { // 当 prior 走到链表末尾的下一位时（即 NULL）
        prior = prior->link;
        rear = rear->link;
    }

    // 4. 返回 rear 指向的结点
    return rear; // 此时 rear 正好指向倒数第 k 个元素
}

更新日志

2025/7/26 11:02

查看所有更新日志

• b684e-docs:408真题-09-ds代码题🚀于 2025/7/26

版权所有

版权归属：代码・生 活・THINKING

许可证：署名 4.0 国际 (CC-BY-4.0)