Java - 使用链表指针进行合并排序

Question

我在为链表实现合并排序时遇到问题，特别是合并部分。我正在尝试对包含字符串的链接列表进行排序并按字母顺序对其进行排序。但是，我的合并代码有时会根据原始列表的顺序出于某种原因跳过指针。目前我有:

public node merge(node left, node right){
        node result = null;

        if(left == null){
            return right;
        }else if(right == null){
            return left;
        }   

        // The data in the node are stored as strings.
        // Compare if the string in the left node is less that 
        // the string in the right.
        if(left.info.compareTo(right.info) < 0){
            result = left;
            result.next = merge(left.next, right);
        }else{
            result = right;
            result.next = merge(left, right.next);
        }

        return result;
    }

如果我有一个由 f->t->c->t->h 组成的列表，我的合并将返回 h->t->t，其中缺少指针。但是，如果我的列表由 b->a->t->t->c 组成，那么它会按字母顺序正确显示它，a->b->c->t->t，并且不会遗漏任何指针。

任何帮助表示赞赏。

谢谢。

Answer 1

我认为这是因为您持有指向左右的旧指针，它们可能不再是子列表的头部。

改变

 mergeSort(left);
 mergeSort(right);

到

 left = mergeSort(left);
 right = mergeSort(right);