单链表合并排序

Question

我试图借助单链表编写合并排序，节点定义如下，

public class Node {

    public int item;
    public Node next;

    public Node(int val) {
        this.item = val;
    }

    public Node() {

    }

    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                ", next=" + next +
                '}';
    }
}

合并排序的工作方式如下：

i、 将未排序的列表划分为n个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。

二、。重复合并子列表以生成新排序的子列表，直到只剩下1个子列表。这将是排序列表。代码如下所示。

public class MergesortWithSinglyLL {

    private Node head;

    public MergesortWithSinglyLL() {
        head = null;
    }

    public boolean isEmpty() {
        return (head == null);
    }

    public void insert(int val) {

        Node newNode = new Node(val);

        newNode.next = head;
        head = newNode;
    }

    // get the end of the queue
    public Node getHead() {
        return head;
    }


    /*
     Initially, this method is called recursively till there will be only one node
     */

    // this mergeSort returns the head of the sorted LL
    public Node mergeSort(Node head) {

        /*
            list is null or just one node is prevail
         */
        if (head == null || head.next == null) {
            return head;
        }

        Node a = head;
        Node b = head.next;

        while ((b != null) && (b.next != null)) {
            head = head.next;
            b = (b.next).next;
        }

        b = head.next;

        // split the list in 2 parts now
        head.next = null;

        return merge(mergeSort(a), mergeSort(b));
    }

    // This is the merge method provided.

    public Node merge(Node a, Node b) {

        Node head = new Node();
        Node c = head;

        while ((a != null) && (b != null)) {

            if (a.item <= b.item) {
                c.next = a;
//                c = a;
                c = c.next;
                a = a.next;
            } else {
                c.next = b;
//                c = b;
                c = c.next;
                b = b.next;
            }
        }

        // define the last element of the ll
        c.next = (a == null) ? b : a;
        return head.next;
    }


    public void display() {

        Node current = head;
        String result = "";

        while (current != null) {
            result += " " + current.item + " ";
            current = current.next;
        }
        System.out.println(result);
    }
}

我像这样打入会电话，

    int[] arr = {12, 3, 4, 56, -7, -6, -5, 1};

    MergesortWithSinglyLL merges = new MergesortWithSinglyLL();

    for (int i = 0; i < arr.length; i++) {
        merges.insert(arr[i]);
    }

    merges.mergeSort(merges.getHead());
    merges.display();

结果是，所有负值似乎都消失了。这里有什么问题？

Answer 1

您的实现很好，错误在您所称的初始化调用中。

MergeSort返回排序列表，但您不分配它，因此您最终会得到解决方案的子集。

如果你更换这条线

merges.mergeSort(merges.getHead());

用这条线

merges.head = merges.mergeSort(merges.getHead());

（当然，您必须公开MergesortWithSinglyLL.head）

结果，您将看到您获得了正确的排序列表。