合并两个链表到一个新的java

Question

我正在尝试将两个排序的链表合并为新的链表。

如l1: 1->3->7和l2: 0->2->10，则l3必须为:0->1->2->3->7->10。

但是它给出了运行时错误:

void Merge(node Head1,node Head2){
    while(Head2!=null || Head1!=null){
        node temp=new node();
        int Head1info=Head1.getInfo();
        int Head2info=Head2.getInfo();
        if(Head1info < Head2info){
            temp.setInfo(Head2.getInfo());
            Head2=Head2.getLink();
        } else{
            temp.setInfo(Head1.getInfo());
            Head1=Head1.getLink();
        }
        if(Tail==null){
            Head=Tail=temp;
        }
        else{
            Tail.setLink(temp);
            Tail=temp;
        }
    }
    if(Head1==null){ 
        while(Head2!=null){
            node temp=new node();
            temp.setInfo(Head2.getInfo());
            Head2=Head2.getLink(); 
            Tail.setLink(temp);
            Tail=temp;
        }
    }
    if(Head2==null){ 
        while(Head1!=null){
            node temp=new node();
            temp.setInfo(Head1.getInfo());
            Head1=Head1.getLink(); 
            Tail.setLink(temp);
            Tail=temp;
        }
    }
}

Answer 1

错误应该是由于这段代码

while(Head2!=null || Head1!=null){

既然你在做

Head1.getInfo() and Head2.getInfo();

所以改成

while(Head2!=null && Head1!=null){

如果其中一个(head1或head2但不是两个)变成NULL，您将在运行时获得NullPointerException

Answer 2

就我个人而言，我会选择这种简单的方式，在O(n*log(n))中工作:

List<T> result= new ArrayList<T>();
result.addAll(list1);
result.addAll(list2);
Collections.sort(result);

与Stream结合使用效果稍好。

Stream resultStream = Stream.concat(list1.stream(), list2.stream()).sorted();
List<String> result = resultStream.collect(Collectors.toList());

我用两个列表测试了第二种方法，每个列表都有超过10,000,000项排序。执行合并大约需要476 milliseconds。

如果你的列表不包含真正的大数据(超过数百万)，性能真的无关紧要。