考研笔记

板子：快慢指针（中点、倒数第 k 个、判环）

两个指针速度不同，或者先拉开一段距离再一起走。这样一趟就能找到和表尾位置有关的结点，不用先求表长。

找中点

LNode *middle(LinkList L) {                  // 返回第 ⌈n/2⌉ 个结点，也就是前半段的最后一个
    LNode *slow = L, *fast = L;              // 都从头结点出发
    while (fast != NULL && fast->next != NULL) {   // 保证 fast->next->next 不会访问空指针
        slow = slow->next;                   // 慢指针走一步
        fast = fast->next->next;             // 快指针走两步
    }
    return slow;                             // 空表时返回头结点 L
}

关键边界：中点停在哪

出发点循环条件1 2 3 41 2 3 4 5停在
头结点 Lfast != NULL && fast->next != NULL23第 个（偶数时是前一个中点）
第一个结点 L->next同上33第 个（偶数时是后一个中点）

要让前半段不短于后半段，就从头结点出发（2019 年重排用的就是这种）。

倒数第 k 个（2009）

int searchK(LinkList list, int k) {          // 2009：找到就输出 data 并返回 1，否则返回 0
    LNode *p = list->next, *q = list->next;
    int cnt = 0;                             // q 领先 p 的步数
    while (q != NULL) {
        if (cnt < k) cnt++;                  // 前 k 步只有 q 走，拉开 k 的距离
        else p = p->next;                    // 之后 p、q 一起走
        q = q->next;
    }
    if (cnt < k) return 0;                   // 表长不足 k
    printf("%d", p->data);                   // q 走到 NULL 时，p 离 NULL 正好 k 步
    return 1;
}

判环与环的入口

bool hasCycle(LinkList L) {                  // 有环时快指针一定会追上慢指针
    LNode *slow = L, *fast = L;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;       // 比较的是地址，不是 data
    }
    return false;                            // fast 走到了 NULL：无环
}
 
LNode *cycleEntry(LinkList L) {              // 返回环的入口结点；无环返回 NULL
    LNode *slow = L, *fast = L;
    while (fast != NULL && fast->next != NULL) {   // 第一步：和 hasCycle 一样，找相遇点
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (fast == NULL || fast->next == NULL) return NULL;   // 是因为走到表尾才退出的：无环
    LNode *p = L, *q = slow;                 // 第二步：一个从起点、一个从相遇点，每次都走一步
    while (p != q) { p = p->next; q = q->next; }
    return p;                                // 再次相遇的位置就是入口
}

为什么第二步能找到入口：设起点到入口 步，入口到相遇点 步，环长 。相遇时慢指针走了 ，快指针走了 ，快指针多走的 一定是整圈，即 。所以从相遇点再走 步，走过的总长是 ，正好回到入口。

复杂度：三个功能都是时间 ，空间 。

易错点

  • 循环条件写 fast != NULL && fast->next != NULL，顺序不能反：&& 先判断左边，fast 是空指针时就不会再去访问 fast->next。
  • 倒数第 k 个： 可能比表长还大，要返回 0。
  • 判环比较的是指针 slow == fast，不是比较两个结点的 data。
  • 2009 年原题的指针字段叫 link，考场上按题目的名字写。

链接

反向链接