文章

78

粉丝

0

获赞

0

访问

3.6k

头像
2009年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年7月23日 19:10
阅读数 62

(1)双指针法(快慢指针):

  1. 初始化两个指针 fast 和 slow,均指向头结点 list

  2. fast 先移动 k 步,使得 fast 和 slow 之间间隔 k 个结点。

  3. 同时移动 fast 和 slow,直到 fast 到达链表末尾(fast->next == NULL)。

  4. 此时 slow 指向倒数第 k 个结点(因为 fast 和 slow 始终保持 k 的间隔)。

  5. 如果 fast 在移动过程中提前到达末尾(链表长度不足 k),则查找失败

(2)

  1. 初始化指针:

    • fast = list->nextslow = list->next(均指向第一个实际结点)。

    • count = 0,记录 fast 已移动的步数。

  2. fast 先移动 k 步:

    • 循环 k 次,每次 fast = fast->nextcount++

    • 如果中途 fast == NULL,说明链表长度不足 k,直接返回 0。

  3. 同步移动 fast 和 slow

    • 循环直到 fast == NULL,每次 fast = fast->nextslow = slow->next

  4. 输出结果:

    slow 即为倒数第 k 个结点,输出 slow->data 并返回 1。

(3)

int FindKthToTail(LinkList list, int k) {
    if (list == NULL || k <= 0) {
        ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发