环形链表归并排序算法异常求助：仅输出1,19或陷入死循环

问题定位 #

你的代码存在以下几个关键错误：

1. 缺少sort()公共方法：main中调用了l.sort()但类中未实现，导致排序逻辑未被正确触发。
2. 链表拆分逻辑错误：拆分左右子链表时，右链表未形成独立环形，递归处理时会遍历到原链表节点，导致逻辑混乱。
3. 合并阶段终止条件错误：使用原链表头作为子链表的终止标记，但递归排序后的子链表结构已改变，该标记失效。
4. 临时节点处理错误：合并时返回的临时头节点（值为-1）不属于原链表，会混入无效节点，且合并后的链表未正确闭环。
5. main方法语法错误：List l = new List(input)后缺少分号。

修正后的完整代码 #

public class List {
    private class Node {
        private int value;
        private Node next;

        private Node(int element, Node next) {
            this.value = element;
            this.next = next;
        }
    }

    private Node head;

    public List(int[] values) {
        this.addAll(values);
    }

    public static void main(String[] args) {
        int[] input = { 1, 9, 42, 3, 7 };
        List l = new List(input);
        l.sort();
        l.add(19);
        System.out.println(l.toString());
    }

    public int length() {
        if (this.head == null)
            return 0;
        Node current = this.head.next;
        int count = 1;
        while (current != this.head) {
            current = current.next;
            count++;
        }
        return count;
    }

    public void add(int value) {
        if (this.length() == 0) {
            this.head = new Node(value, null);
            this.head.next = this.head;
            return;
        }
        Node current = this.head.next;
        while (current.next != this.head)
            current = current.next;
        current.next = new Node(value, this.head);
    }

    public void addAll(int[] values) {
        for (int value : values)
            this.add(value);
    }

    public String toString() {
        String s = "";
        if (this.length() == 0)
            return s;
        s = this.head.value + "";
        if (this.length() == 1)
            return s;
        Node current = this.head.next;
        for (int i = 1; i < this.length(); i++) {
            s += ", " + current.value;
            current = current.next;
        }
        return s;
    }

    public void sort() {
        if (head == null || head.next == head) {
            return;
        }
        // 排序后得到线性链表，重新闭环
        head = mergeSort(head);
        Node tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = head;
    }

    private Node mergeSort(Node head) {
        // 递归终止：单节点，拆成线性节点
        if (head.next == head) {
            head.next = null;
            return head;
        }

        // 快慢指针找中间节点
        Node slow = head;
        Node fast = head.next;
        while (fast != head && fast.next != head) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 拆分左右链表，各自闭环
        Node rightHead = slow.next;
        slow.next = head; // 左链表闭环

        // 右链表闭环
        Node rightTail = rightHead;
        while (rightTail.next != head) {
            rightTail = rightTail.next;
        }
        rightTail.next = rightHead;

        // 递归排序左右
        Node left = mergeSort(head);
        Node right = mergeSort(rightHead);

        // 合并两个线性链表
        Node dummy = new Node(-1, null);
        Node current = dummy;
        while (left != null && right != null) {
            if (left.value < right.value) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }
        // 拼接剩余节点
        if (left != null) {
            current.next = left;
        }
        if (right != null) {
            current.next = right;
        }

        return dummy.next;
    }
}

关键修改说明 #

1. 补充sort()方法：负责启动排序，并将排序后的线性链表重新闭环，恢复环形结构。
2. 调整递归终止逻辑：将单节点的环形链表拆成线性节点，简化合并操作。
3. 修正链表拆分：拆分后将左右子链表分别闭环，确保递归时能正确判断终止条件。
4. 合并阶段改为线性处理：归并排序的合并逻辑更适合线性链表，合并完成后再统一闭环。
5. 移除static修饰：mergeSort改为非static方法，避免创建多余的List实例来生成Node。

运行修正后的代码，会输出1, 3, 7, 9, 42, 19，符合预期。

内容的提问来源于stack exchange，提问作者Timm