java - 合并排序未给出正确的输出

Question

我有两门课:

public class List {
    public Node _head;
}

还有:

public class Node {
    public String _word;
    public Node _next;
}

我在“List”中有一个构造函数，它获取一个字符串作为参数，并将每个单词放入一个单独的节点中，如下所示:

public List(String text) {
    if (text.length() == 0)
        _head = null;
    createList(text);
}

private void createList(String text) {
    int lastIndex=0; 
    String temp;        
    for (int i=0;i<text.length();i++) {
        if (text.charAt(i)==' '|| i==text.length()-1) {
            if (i == 0) { // Space in the begining
                lastIndex=1;
                continue;
            }
            if (i == text.length()-1) { // If we reached to the last char of the string

                if (text.charAt(i) == ' ') { // If it's a space, don't include it
                    temp = text.substring(lastIndex,i);
                } else {
                    temp = text.substring(lastIndex,i+1);
                }
            } else {
                temp = text.substring(lastIndex,i);
            }
            addToBegining(temp);
            lastIndex=i+1;
        }
    }
}

无论如何，当我尝试在链接列表上使用合并排序时，我无法使其正常工作。

这是排序代码:

public Node merge_sort(Node h) {
    if (h == null || h._next == null) { return h; }
    Node middle = getMiddle(h);      //get the middle of the list
    Node sHalf = middle._next; middle._next = null;   //split the list into two halfs

    return merge(merge_sort(h), merge_sort(sHalf));  //recurse on that
}

public Node merge(Node a, Node b) {
    Node dummyHead, curr; 
    dummyHead = new Node(); 
    curr = dummyHead;
    while (a !=null && b!= null) {
        if (a._word.compareTo(b._word) <= 0) { 
            curr._next = a; 
            a = a._next; 
        } else { 
            curr._next = b; 
            b = b._next; 
        }
        curr = curr._next;
    }
    curr._next = (a == null) ? b : a;
    return dummyHead._next;
}

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

知道出了什么问题吗？我正在尝试使用字符串“Hello New World A Dawn Is There”创建一个新的 TextList，输出为:“There World”..

Answer 1

请进行如下更改。我认为您忘记将 curr 节点分配给 if-else 之后的适当值。

    public Node merge(Node a, Node b)
    {
        Node dummyHead, curr;
        dummyHead = new Node();
        curr = dummyHead;
        while (a != null && b != null)
        {
            if (a._word.compareTo(b._word) <= 0)
            {
                curr._next = a;
                curr = a;
                a = a._next;
            }
            else
            {
                curr._next = b;
                curr = b;
                b = b._next;
            }
            curr = curr._next;
        }
        curr._next = (a == null) ? b : a;
        return dummyHead._next;
    }