java - 与字符串的合并排序

Question

我在名为 WordNode 的类中有一个链表，它包含以下属性:

String _word; WordNode _next;

我有另一个类，它是“实际列表”，它只保存对列表头部的引用，该类称为 TextList ，它接收一个 String并应该将 String 中的每个单词都排序在列表中。例如，对于句子:

coding in Java is cool.

链接列表如下所示:

coding >>> cool >>> Java >>> in >>> is.

箭头就像指向列表中下一个节点的指针。

我想首先将所有单词放入一个链接列表(TextList 类)中，然后进行 MERGE SORT 对链接列表中的单词进行排序。

我想做的是采用 split 方法将列表拆分为两个列表:“奇数”和“偶数”，这就是这些方法:

private TextList splitOdds(){
    boolean flag=true;
    TextList odds=new TextList();
    WordNode o=null;
    WordNode ptr=_head;
    while (ptr.getNext()!=null){
        if(flag)
            o=new WordNode(ptr.getWord(),o);
        ptr=ptr.getNext();
         flag=!flag;
    }
    odds._head=o;;
    return odds;
}

private TextList splitEvens(){
    boolean flag=true; 
    TextList evens=new TextList();
    WordNode e=null;
    WordNode ptr=this._head.getNext();
    while (ptr!=null){
        if(flag)
            e=new WordNode(ptr.getWord(),e);
        ptr=ptr.getNext();
        flag=!flag;
    }
    evens._head=e;
    return evens;
}

拆分确实有效。

但我不知道从这里继续哪里。我想递归地调用 split 方法并拆分列表，直到它是一个或两个节点的列表，但我不知道如何做到这一点。

编辑:不能使用第三类，禁止练习。还保存 TextList 的长度。仅通过 WordNode 类上的属性保存每个单词出现的次数。

Answer 1

这当然是假设您在每次插入或删除时保留列表的长度。您所要做的就是像这样将列表分成两半，同时保留原始列表的头/根。在实现合并排序时，您甚至不需要任何中间列表。

    LinkedList LinkedList::split(){
            _Node_* p=head, *q=p;
            for(int i=0; i<len/2; i++){
                    q=p;
                    p=p->next;
            }
            LinkedList ret;
            ret.head=p;
            ret.len=len-len/2;
            len=len/2;
            q->next=NULL;
            return ret;
    }