一、循环链表死循环的常见场景

先给大家举个生活里的例子,方便理解循环链表:你买了一串带挂环的钥匙,每个挂环上挂着一把钥匙,最后一个挂环的环扣直接扣回了第一个挂环上——这就是循环链表的原型,正常情况下你按顺序摸钥匙,摸完最后一个会绕回第一个,不会断。但如果某两个挂环互相扣住,比如第二个挂环扣回了第一个,第一个又扣回了第二个,你摸钥匙就会在这两个环之间转圈圈,永远摸不到其他钥匙,这就是死循环。

放到代码里,循环链表死循环的核心就是某个节点的next指针(就是挂环的环扣)指向了前面已经出现过的节点,导致遍历的时候绕不出来。接下来给大家说几个最容易踩坑的场景。

1.1 链表构建时的逻辑错误

很多新手写循环链表的时候,容易在“收尾”步骤出错。比如要做一个3个节点的循环链表,本来应该让最后一个节点的next指向头节点,结果不小心写成了指向中间节点。

1.2 链表修改时的误操作

循环链表用久了经常会修改,比如插入节点、删除节点,这时候最容易改坏指针。比如插入一个新节点,本来要把新节点的next指向原来的节点,再把原来的前一个节点的next指向新节点,结果搞反了顺序,或者漏改某个指针,就可能把链改断,变成局部循环。

1.3 遍历逻辑的漏洞

有些死循环不是链表本身有问题,是遍历的时候没写对判断条件。比如循环链表的遍历应该以“回到头节点”作为结束标志,结果你写成了“当前节点不为空”,那遍历就会一直绕圈,永远停不下来。

二、死循环的触发条件定位方法

死循环出现后,最头疼的就是找不到问题在哪,毕竟链表是动态的,打印出来的日志也可能是绕圈的片段。接下来给大家说两个实用的定位方法,都是能直接上手用的。

2.1 快慢指针法(Floyd判圈算法)

这个方法的原理特别好懂:你想象两个人绕操场跑步,一个跑的快一个跑的慢,如果操场是直的,那快的人会越来越远;如果操场是环形的,那快的人迟早会追上慢的人。放到链表上,就是用两个指针,一个每次走1步(慢指针),一个每次走2步(快指针),如果链表有环,两个指针一定会相遇;如果没环,快指针会先走到链表末尾(空节点)。

这里给大家举个完整的示例,技术栈统一用Java,先写一个带死循环的循环链表,再用快慢指针定位:

// 定义链表节点类
class ListNode {
    int val; // 节点的值
    ListNode next; // 节点的下一个指针
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class CycleLinkedListDemo {
    public static void main(String[] args) {
        // 构建一个有死循环的链表:1 -> 2 -> 3 -> 2(这里故意让3的next指向2,形成2<->3的循环)
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next = node2;
        node2.next = node3;
        node3.next = node2; // 错误的指向,触发死循环

        // 用快慢指针定位死循环
        boolean hasCycle = hasCycle(head);
        System.out.println("链表是否存在死循环:" + hasCycle);
    }

    /**
     * 快慢指针判断链表是否有环的方法
     * @param head 链表的头节点
     * @return true表示有环(死循环),false表示无环
     */
    private static 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; // 慢指针走1步
            fast = fast.next.next; // 快指针走2步
            // 两个指针相遇,说明有环
            if (slow == fast) {
                return true;
            }
        }
        // 快指针走到末尾,说明没有环
        return false;
    }
}

这个示例运行后会输出“链表是否存在死循环:true”,就能快速定位到链表有问题。

2.2 哈希表标记法

这个方法的原理也很简单:遍历链表的时候,把每个已经访问过的节点存到哈希表里,每次访问新节点的时候,先查哈希表,如果已经存在,说明这个节点之前访问过,就形成了死循环。

还是用刚才的错误链表,给大家写一个哈希表定位的示例:

import java.util.HashSet;
import java.util.Set;

public class CycleCheckByHash {
    public static void main(String[] args) {
        // 构建和之前一样的错误链表:1 -> 2 -> 3 -> 2
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next = node2;
        node2.next = node3;
        node3.next = node2;

        boolean hasCycle = hasCycleByHash(head);
        System.out.println("链表是否存在死循环:" + hasCycle);
    }

    private static boolean hasCycleByHash(ListNode head) {
        // 用哈希表存储已经访问过的节点
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            // 如果当前节点已经在哈希表中,说明有环
            if (visited.contains(current)) {
                return true;
            }
            // 把当前节点加入哈希表
            visited.add(current);
            // 移动到下一个节点
            current = current.next;
        }
        // 遍历完所有节点,没有环
        return false;
    }
}

这个方法的好处是,除了能判断有没有环,还能拿到环的入口节点,适合需要修复死循环的场景。

三、死循环的解决方法

定位到死循环后,接下来就是解决问题,这里分两种情况:一种是修复死循环,让链表恢复正常;另一种是避免死循环的出现,从源头预防。

3.1 修复死循环

修复死循环的核心就是找到环的入口,然后把环断开,改成正常的循环链表(如果是业务需要循环的话)或者改成单向链表(如果不需要循环的话)。

比如刚才的错误链表,环的入口是节点2,我们可以把节点3的next改成头节点1,这样就变成了正常的循环链表:1->2->3->1,遍历的时候会以回到头节点作为结束。

给大家写一个完整的修复示例:

import java.util.HashSet;
import java.util.Set;

public class FixCycle {
    public static void main(String[] args) {
        // 构建错误链表:1 -> 2 -> 3 -> 2
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next = node2;
        node2.next = node3;
        node3.next = node2;

        // 先判断有没有环
        if (hasCycleByHash(head)) {
            System.out.println("修复前:链表存在死循环");
            // 修复死循环,改成正常的循环链表:最后一个节点指向头节点
            fixCycle(head);
            System.out.println("修复后:链表已无死循环");
            // 验证修复结果,遍历链表,直到回到头节点停止
            ListNode current = head;
            do {
                System.out.print(current.val + " ");
                current = current.next;
            } while (current != head);
        }
    }

    private static boolean hasCycleByHash(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                return true;
            }
            visited.add(current);
            current = current.next;
        }
        return false;
    }

    private static void fixCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        ListNode prev = null;
        while (current != null) {
            if (visited.contains(current)) {
                // 找到环的位置,把前一个节点的next指向头节点,修复成正常循环
                prev.next = head;
                return;
            }
            visited.add(current);
            prev = current;
            current = current.next;
        }
    }
}

这个示例运行后,会输出“修复前:链表存在死循环”“修复后:链表已无死循环”,然后遍历输出“1 2 3”,说明修复成功。

3.2 预防死循环

最好的解决方法是从源头避免死循环的出现,这里给大家说几个实用的注意事项: 第一,构建循环链表的时候,收尾步骤一定要写对,最后一个节点的next必须指向头节点,不能指向其他节点; 第二,修改链表(插入、删除节点)的时候,一定要按顺序改指针,比如插入节点的时候,先把新节点的next指向原来的下一个节点,再把原来的前一个节点的next指向新节点,不能搞反; 第三,遍历循环链表的时候,一定要以“回到头节点”作为结束标志,不能用“当前节点不为空”,因为循环链表的节点永远不会为空; 第四,复杂的链表操作,一定要加单元测试,比如测试插入、删除节点后,链表有没有死循环。

四、应用场景、技术优缺点及注意事项

4.1 应用场景

循环链表的死循环场景主要出现在以下几种业务场景里: 第一,游戏开发里的角色移动,比如角色在环形地图里移动,链表用来存储路径点,要是路径点的指针出错,角色就会在两个点之间来回跑; 第二,队列实现,比如循环队列,用循环链表存储队列元素,要是队列的指针出错,就会导致队列永远取不完元素; 第三,链表相关的算法题,比如判断链表是否有环、链表的反转、链表的排序等,这些算法题里经常会出现死循环的坑; 第四,底层数据结构的实现,比如操作系统的进程调度、内存管理等,要是用循环链表实现的话,死循环会导致系统崩溃。

4.2 技术优缺点

快慢指针法的优点是空间复杂度低,只需要两个指针,不需要额外的存储空间,适合处理大规模的链表;缺点是只能判断有没有环,不能直接拿到环的入口,需要额外的步骤才能定位环的位置。 哈希表标记法的优点是能直接拿到环的入口,定位问题更准确,适合需要修复死循环的场景;缺点是空间复杂度高,需要额外的存储空间来存储已经访问过的节点,不适合处理大规模的链表。

4.3 注意事项

第一,定位死循环的时候,一定要先判断链表是否为空,或者只有一个节点的情况,避免出现空指针异常; 第二,修复死循环的时候,一定要确认业务需求,要是业务需要循环链表,就把环改成指向头节点;要是业务不需要循环链表,就把环断开,改成单向链表; 第三,遍历循环链表的时候,一定要用do-while循环,不能用while循环,因为头节点一开始就访问了,用while循环的话会直接跳过第一个节点; 第四,复杂的链表操作,一定要加日志,比如插入、删除节点的时候,打印出前后节点的指针,方便后续排查问题。

五、文章总结

循环链表的死循环是很多开发者都会踩的坑,核心原因是指针指向错误,导致遍历的时候绕不出来。定位死循环的方法主要有快慢指针法和哈希表标记法,各有优缺点,大家可以根据自己的业务场景选择。解决死循环的方法主要有修复死循环和预防死循环,修复死循环的核心是找到环的入口,然后断开环;预防死循环的核心是从源头避免指针错误,比如构建、修改链表的时候注意指针的顺序,遍历的时候注意结束标志,加单元测试等。

只要大家掌握了这些方法,以后遇到循环链表死循环的问题,就能快速定位和解决,不会再被绕得晕头转向。