Java合并排序在链表上仅在添加最小数字时进行排序

Question

当我在我的链表中插入数字时，只有当添加到该链表的第一个数字是最小的时，它才会对所有内容进行排序。这是我所遇到的意外行为：

我按照以下顺序插入数字-200、25、473、23、390。

如果我像上面那样对列表进行排序并显示它，我会得到这个结果——200、390、473。

如果我将200更改为900，然后对列表进行排序，它只会显示900。

只有当我将200更改为列表中最小的数字，比如1（或任何小于23的数字），然后它才会给出正确的输出：1、23、25、390、473。

对于此链接列表，我在列表后面插入元素，这是代码：

public void insertAtBack(IntegerElement elem) {
    if (isFull()) {
        System.out.println("Unable to insert node into full list");
    } else {
        Node temp = new Node(elem);
        if (isEmpty()) {
            head = temp;
        } else {
            Node current = head;
            while (current.getLink() != null) {
                current = current.getLink();
            }
            current.setLink(temp);
        }
    }

}

这是我用来进行归并排序的代码：

public Node getMiddle(Node node) {
    if (node == null) 
        return node;

    Node fastptr = node.getLink(); 
    Node slowptr = node; 

    // Move fastptr by two and slow ptr by one 
    // Finally slowptr will point to middle node 
    while (fastptr != null) { 
        fastptr = fastptr.getLink(); 
        if(fastptr != null) { 
            slowptr = slowptr.getLink(); 
            fastptr = fastptr.getLink(); 
        } 
    } 

    return slowptr; 
}

public Node merge(Node left, Node right)  { 

    Node tempHead = new Node(), curr;

    curr = tempHead;

    while(left != null && right != null) {
        if(left.getData().getValue() <= right.getData().getValue()) {
            curr.setLink(left);
            left = left.getLink();
        }else {
            curr.setLink(right);
            right = right.getLink();
        }

        curr = curr.getLink();
    }

    curr.setLink((left == null) ? right : left);

    return tempHead.getLink();

}

/**
 * This method utilizes merge sort algorithm
 * 
 * @param node - Pass in head first
 * 
 */
public Node sort(Node node) {
    // Base case : if head is null 
    if (node == null || node.getLink() == null)
        return node; 

    // get the middle of the list 
    Node middle = getMiddle(node);
    Node nextofmiddle = middle.getLink();

    // set the next of middle node to null 
    middle.setLink(null);

    // Merge the left and right lists 
    return merge(sort(node), sort(nextofmiddle));
}

非常感谢您的帮助

- chinloyal

---

请提供一个最小、完整、可验证的示例。 - samabcde

Answer 1

你的排序程序看起来很好。错误似乎出现在你从排序程序返回的方式上。如果你把它当作原地排序调用，即...

sort(head);
System.out.println(head);

旧头部没有更新为sort()返回的新头部。请注意，在您的测试用例中显示的节点始终以旧头部开头。如果未排序列表中的旧头部恰好是排序列表中的新头部，则似乎可以正常工作，就像您最后一个示例中一样。另一方面，如果在排序过程中移动了旧头结点，则只会从旧头移动到的位置开始看到列表的其余部分。从列表前面到旧头的节点将在超出范围时被垃圾回收。

解决方法是在调用者中将列表的头部设置为sort()返回的头部，这是列表的新头部：

head = sort(head);
System.out.println(head);

这是您的代码重写，用于重现错误以说明问题：

class Main {
    public static void main(String[] args) {
        Node head = new Node(200, new Node(25, new Node(473, new Node(23, new Node(390, null)))));

        System.out.println("Example 1 (correct):");
        System.out.println(head);
        head = sort(head);
        System.out.println(head);

        head = new Node(200, new Node(25, new Node(473, new Node(23, new Node(390, null)))));

        System.out.println("\nExample 1 (incorrect):");
        System.out.println(head);
        sort(head);
        System.out.println(head);

        head = new Node(900, new Node(25, new Node(473, new Node(23, new Node(390, null)))));

        System.out.println("\n\nExample 2 (correct):");
        System.out.println(head);
        head = sort(head);
        System.out.println(head);

        head = new Node(900, new Node(25, new Node(473, new Node(23, new Node(390, null)))));

        System.out.println("\nExample 2 (incorrect):");
        System.out.println(head);
        sort(head);
        System.out.println(head);

        head = new Node(1, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
        System.out.println("\n\nExample 3 (accidentally works, because the old head is still the new head):");
        System.out.println(head);
        sort(head);
        System.out.println(head);
    }

    static Node getMiddle(Node node) {
        Node fastptr = node.link; 
        Node slowptr = node; 

        while (fastptr != null) { 
            fastptr = fastptr.link; 

            if (fastptr != null) { 
                slowptr = slowptr.link;
                fastptr = fastptr.link; 
            }
        } 

        return slowptr; 
    }

    static Node merge(Node left, Node right) { 
        Node temp = new Node(-1, null);
        Node curr = temp;

        while (left != null && right != null) {
            if (left.data < right.data) {
                curr.link = left;
                left = left.link;
            }
            else {
                curr.link = right;
                right = right.link;
            }

            curr = curr.link;
        }

        curr.link = left == null ? right : left;
        return temp.link;
    }

    static Node sort(Node node) {
        if (node == null || node.link == null) {
            return node; 
        }

        Node middle = getMiddle(node);
        Node next = middle.link;
        middle.link = null;
        return merge(sort(node), sort(next));
    }
}

class Node {
    public int data;
    public Node link;

    public Node(int data, Node link) {
        this.data = data;
        this.link = link;
    }

    public String toString() {
        return this.data + (this.link != null ? "->" + this.link : "");
    }
}

输出：

Example 1 (correct):
200->25->473->23->390
23->25->200->390->473

Example 1 (incorrect):
200->25->473->23->390
200->390->473


Example 2 (correct):
900->25->473->23->390
23->25->390->473->900

Example 2 (incorrect):
900->25->473->23->390
900


Example 3 (accidentally works, because the old head is still the new head):
1->25->473->23->390
1->23->25->390->473

试一下！

- ggorlen