0

マージソートを使用してリンクリストをソートしようとしてきたので、このコードを見つけて作業しようとしましたが、実際には機能していませんか?

何が問題なのですか？リスト自体から2つのリストを操作するには、リストの中間値を取得する必要があることはわかっていますが、getMiddleメソッドについてはよくわかりません

コードは次のとおりです。

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();
4

1 に答える 1

1

1 つの問題は、getMiddleメソッドが正しく middle を返さないことNodeです。

5 つのノード (a、b、c、d、e) を持つ連結リストを考えてみましょう

head、slow、およびfastすべてインデックス 0 から始まります (a)。

whileループの最初の繰り返しの後、slowは 1 (b) でfastあり、 2 (c) です。2 回目の反復の後、slow2 (c) で高速になり、4 (e) で高速になります。これらは両方とも null ではないため、別の反復が発生し、3 (d) で遅く、 で速くなりnullます。fastは null であるため、ループwhileを終了しslowて返されます。ただしslow、中間ノード 2 (c) ではなく、ノード 3 (d) があります。

中間ノードを取得する別の方法は、単純にノード数を使用することです。

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;
}

私はあなたの方法は問題ありませんが、技術的には、それ自体が isの場合ではなく、isの場合mergeSortにのみ返す必要があります(とにかくそれは決して起こらないため):headhead.linknullheadnull

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
}
于 2013-10-31T15:47:52.547 に答える