刷到外企外包30k和甲方19k纠结贴，顺便写个环形链表

刚刷到这个帖子，给我看愣了一下。一个外企外包30k，一个外企甲方19k，楼主自己也说都不太稳，在那儿纠结选谁。

外包这边就是钱给得猛，但项目一收人就散，听起来像随时被“优化”。甲方这边工资少点，但也没好到哪去，裁员一样照来，只是节奏慢一点。

评论区估计也吵不出啥统一答案，打工人看完基本都是沉默，这题怎么选都像在开盲盒，手一抖就是不同人生走向了……

今日面试题

链表遍历到一半，程序不报错，也不返回。

这种题我第一眼不会去怀疑递归，也不会上来就数节点。链表这种结构，一旦出现“跑不完”，八成是指针绕回去了，也就是环形链表。

最容易写错的办法，是拿一个 HashSet 存访问过的节点：

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    ListNode cur = head;
    while (cur != null) {
        if (seen.contains(cur)) {
            return true;
        }
        seen.add(cur);
        cur = cur.next;
    }
    return false;
}

这段代码能过，思路也直观。

每走到一个节点，就看这个节点之前有没有来过。如果来过，说明链表里有环；如果一直走到 null，说明没有环。

但我不太喜欢这个写法。

不是它错，而是它多用了一个集合。链表题里，能用指针解决的，我一般不会先上容器。面试里也一样，你写 HashSet，对方多半会继续问：不用额外空间怎么做？

这时候就得用快慢指针。

慢指针一次走一步，快指针一次走两步。

如果链表没有环，快指针肯定先走到 null。

如果链表有环，快指针进环之后，会在环里一圈一圈追慢指针。别看一个走一步，一个走两步，它们一定会撞上。这个地方不用想复杂，就像操场跑圈，跑得快的人迟早会套圈。

代码我一般这么写：

public class CycleChecker {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

节点结构也放一下，别脑补：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

这里有个细节，while 条件必须写成：

while (fast != null && fast.next != null)

不能只判断 fast != null。

因为快指针每次要走两步：

fast = fast.next.next;

如果 fast.next 已经是 null，再取 .next 就直接空指针了。算法题里这种错很烦，逻辑没问题，边界炸了。

可以手动构造一个链表测一下：

ListNode a = new ListNode(1);
ListNode b = new ListNode(2);
ListNode c = new ListNode(3);
ListNode d = new ListNode(4);

a.next = b;
b.next = c;
c.next = d;
d.next = b; // 这里把尾巴接回第二个节点

System.out.println(new CycleChecker().hasCycle(a)); // true

如果把最后一行改成：

d.next = null;

结果就是 false。

这题真正要记的不是“快慢指针”四个字，而是判断顺序。

先保证快指针还能走两步，再移动指针，再判断是否相遇。顺序乱了，有些很短的链表就会出问题。

时间复杂度是 O(n)，每个节点最多被指针扫过有限次。

空间复杂度是 O(1)，没有额外集合。

环形链表这题看着简单，但它其实在考一个习惯：遇到链表跑不完，不要先想着硬遍历，先看看是不是有环。指针题很多坑，不在公式里，在那几个 null 判断里。