因此,我一直在尝试使用合并排序对链接列表进行排序,我找到了这段代码并尝试对其进行处理,但是它似乎没有真正起作用吗?

可能是什么问题?我不太了解getMiddle方法,尽管我知道它应该获取列表的中间值才能处理列表本身中的2个列表

这是代码;

public Node mergeSort(Node head) {

    if (head == null || head.link == null) {
        return head;
    }

    Node middle = getMiddle(head);

    Node sHalf = middle.link;
    middle.link = null;

    return merge(mergeSort(head), mergeSort(sHalf));
}

public Node merge(Node a, Node b) {
    Node dummyHead;
    Node current;

    dummyHead = new Node();
    current = dummyHead;

    while (a != null && b != null) {
        if ((int) a.getData() <= (int) b.getData()) {
            current.link = a;
            a.link = a;
        }
        else {
            current.link = b;
            b.link = a;
        }
        current = current.link;
    }
    current.link = (a == null) ? b : a;
    return dummyHead;
}

public Node getMiddle(Node head) {
    if (head == null) {
        return head;
    }
    Node slow, fast;
    slow = fast = head;
    while (fast.link != null && fast.link.link != null) {
        slow = slow.link;
        fast = fast.link.link;
    }
    return slow;
}


在主要方法中:

  Object data;
    MyLinkedList list = new MyLinkedList();         //empty list.


    for (int i = 0; i < 3; i++) {           //filling the list
        data = console.nextInt();
        list.insertAtFront(data);
    }


    System.out.print("Print(1): ");
    list.printList();

   list.mergeSort(list.getHead());
    System.out.print("List after sorting: ");
    list.printList();

最佳答案

一个问题是getMiddle方法不能正确返回中间的Node

考虑一个具有5个节点(a,b,c,d,e)的链表

headslowfast都从索引0(a)开始。

while循环的第一次迭代之后,slow处于1(b),而fast处于2(c);在第二次迭代之后,slow处于2(c)并快速达到4(e)。它们都不为空,因此发生另一次迭代,将慢速设为3(d),将快速设为null。由于fast为null,因此退出while循环并返回slow;但是slow具有节点3(d)而不是中间节点2(c)。

获取中间节点的另一种方法是仅使用节点数:

public Node getMiddle(Node head) {
    Node counter = head;
    int numNodes = 0;
    while(counter != null) {
        counter = counter.link;
        numNodes++;
    }
    if(numNodes == 0)
        return null;
    Node middle = head;
    for(int i=0; i<numNodes/2; i++)
        middle = middle.link;
    return middle;
}


我的mergeSort方法很好,但是从技术上讲,如果headhead.link,则仅需要返回null,而不是head本身是null(因为无论如何都不会发生):

public Node mergeSort(Node head) {
    if (head.link == null) {
        return head;
    }
    // same
}


最重要的是,您的merge方法。您可以在public void setData(Object)类中编写一个Node方法,以使其更容易。以下代码应该可以工作,尽管我不能断言这是完成这项工作的最好/最有效的方法

public Node merge(Node a, Node b) {
    Node combined = new Node();
    Node current = combined;
    while(a != null || b != null) {
        if(a == null)
            addNode(current, b);
        if(b == null)
            addNode(current, a);
        if((int)a.getData()<(int)b.getData())
            addNode(current, a);
        else
            addNode(current, b);
    }
    return combined;
}


使用以下辅助方法:

public void addNode(Node n1, Node n2) {
    n1.setData((int)n2.getData());
    n1.link = new Node();
    n1 = n1.link;
    n2 = n2.link
}

关于java - 合并排序到链表上,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19710854/

10-12 16:28