尝试对链表进行排序

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

list_b 引用包含 3 的节点，并将节点 2 作为下一个元素。

然后你对列表进行排序。这改变了包含 3 的节点：它的下一个节点现在为空，因为它成为列表的最后一个元素。它还更改了节点 2，它现在将节点 3 作为下一个元素。但是 list_b 仍然是对包含 3.

的节点的引用

当您打印节点 list_b 时，您将得到 3, null 作为结果。

编辑：

回答你的最后一个问题：

how you would change the sort method itself so that updating is unnecessary

您应该有一个实际的 LinkedList class（与标准 java.util.LinkedList class 完全一样）。您拥有的 class 不代表列表。它代表节点链中的一个节点。

LinkedList class 将具有对头节点的引用，并将包含迭代存储在列表中的值、将其转换为字符串、对其进行排序等所需的所有方法。当然，对列表进行排序意味着更改对 LinkedList 对象内头节点的引用。但这对 LinkedList class 的用户来说是透明的，他们永远不会直接操作节点。

当然，如果您开始非常关心拥有一个合适的 LinkedList class，您应该简单地使用标准的，它是标准的、有文档记录的和经过测试的。

Answer 2

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

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

列表是这样转换的：

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

sut.sort returns 列表的新前面（头），应该是新的list_b，但是由于你不更新值，它指向列表中的第二个节点，因此产生 "3 , null"

Answer 3

嗯...您正在更改 sort 方法中传递的节点的内部结构。变量 list_b 仍然引用排序后不再有后继节点的节点“3”。

您的排序方法正在返回排序列表的新头。但是你以后不要用它！

将您的代码片段更改为：

list_b = sut.sort(list_b, int_comparator);
System.out.println(sut.convertToString(list_b));

尝试对链表进行排序

Attempting to sort a linked list

java

debugging

linked-list