我无法找到此合并排序算法不起作用的原因

Question

我必须为带有一堆方法的作业创建一个封闭的链接列表类（此处仅显示相关的方法），并且我无法完成最后一个为其添加排序算法的任务。如果我尝试改变所有发生的事情，我只能得到“1, 19”的输出，我陷入了无限循环。我知道我在某个地方犯了一些超级愚蠢的简单而明显的错误，但我自己似乎无法找到它，非常感谢您的帮助，谢谢。

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;
    }


    private static Node mergeSort(Node pHead) {
        if (pHead.next == pHead)
            return pHead;
        Node slow = pHead, fast = pHead.next;
        while (fast != pHead) {
            fast = fast.next;
            if (fast == pHead)
                break;
            slow = slow.next;
            fast = fast.next;
        }
        Node left = pHead, right = slow.next, temp = new List().new Node(-1, null), tempHead = temp;
        slow.next = pHead;
        left = mergeSort(left);
        right = mergeSort(right);
        while (!(left == pHead || right == pHead)) {
            if (left.value < right.value) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        while (left != pHead || right != pHead) {
            if (left != pHead) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        return tempHead;
    }

我尝试缩小范围，但我不太相信这一点，而且遗憾的是我未能查明问题所在。

Answer 1

你的

add

方法似乎不对。

this.head = new Node(value, null); this.head.next = this.head;

/

current.next = new Node(value, this.head);

创建一个循环链表，但您希望链表以

null

终止；您应该使用

null

作为最后一个元素的

next

字段。这可以解释“无限循环”。