java - 尝试对链接列表进行排序

Question

我已经知道这个问题的各种答案。但我的代码中有一个非常令人困惑的错误。下面是一系列 println() 调用，以查看我创建的列表是否已正确排序。

ListNode list_b = new ListNode(3, new ListNode(-2));
System.out.println("Checking the string conversion: " +
sut.convertToString(list_b));    //output is 3,-2, as expected. Expected result of sorting is -2,3.

System.out.println("Now checking the 
string conversion of the sorted list: " +
sut.convertToString(sut.sort(list_b, int_comparator))); //output is -2,3 as expected.

System.out.println("Now this is list_b following the sorting,
by calling the element and next directly: " 
+ list_b.element + "," + list_b.next);      //3,null. How the hell did that happen!?!??!!?

convertToString方法如下:

public String convertToString(ListNode head) {
    if (head != null) {
        String representation = "";
        if (!head.element.equals(null))
            representation += head.element.toString();
        ListNode next = null;
        if (head.next != null)
            next = head.next;
        if (next != null && !next.element.equals(null))
            representation += "," + next.element.toString();
        while (next != null) {
            if (next.next != null) {
                next = next.next;
                if (!next.element.equals(null))
                    representation += "," + next.element.toString();
            }
            else
                break;
        }
        return representation;
    }
    else
        return "";
}

实际的排序方法仍在进行中，尽管相当简单:

public ListNode sort(ListNode head, Comparator comparator) {
    if (head != null) {
        ListNode next = null;
        if (head.next != null)
            next = head.next;
        else
            return head;
        if (comparator.compare(head.element, next.element) > 0) {
            head.next = next.next;
            next.next = head;
            head = next;
        }
        return head;
    }
    return null;
}

有人愿意解释一下我是如何做到看似不可能的事情的吗？我无语了，怎么会发生这样的事!非常感谢任何能解释的人!

编辑:感谢您的回答和建议。我应该澄清一下，然后在列表上执行以下测试:

assertTrue(sut.deepEquals(list_a, sut.sort(list_a, int_comparator)));
assertFalse(sut.deepEquals(list_b, sut.sort(list_b, int_comparator)));

assertTrue(sut.deepEquals(new ListNode(-2, new ListNode(3)), sut.sort(list_b, int_comparator)));
assertTrue(sut.deepEquals(new ListNode(-14, new ListNode(-2, new ListNode(3))), sut.sort(list_c, int_comparator)));

显然，这意味着 list_b 的任何更新(即 list_b = sut.sort(list_b))都是不必要的。我要问的是如何更改排序方法本身，以便不需要更新。

Answer 1

非常简单:您可以在这段代码中对列表进行排序:

sut.convertToString(sut.sort(list_b, int_comparator)))

列表以这种方式转换:

3 -> -2 -> null  ====> -2 -> 3 -> null
^                            ^
|                            |
list_b                       list_b

sut.sort 返回列表的新前面(头)，它应该是新的 list_b，但由于您没有更新该值，所以它指向到列表中的第二个节点，从而产生 "3 , null"