CODEWITHSUNDEEP
javaexceptionlinked-listsingly-linked-list
Riya kathil
Riya kathil

Reputation: 19

Merging two linked list into new one java

I am trying to merge two sorted Linked List into new Linked-List.

like l1: 1->3->7 and l2: 0->2->10 then l3 must be : 0->1->2->3->7->10.

But it is giving run time error:

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

Upvotes: 1

Views: 105

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13924

The error should be because of this code

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

since you are doing

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

So change it to 

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

If one of them(head1 or head2 but not both) becomes NULL, you will get NullPointerException during runtime.

Upvotes: 1

Nikolas
Nikolas

Reputation: 44378

Personally, I'd go for this simple way that works in O(n*log(n)):

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

Combining with Stream is slighty better.

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

I have tested the second way with two lists each with over 10,000,000 items sorted. It took roughly 476 milliseconds to perform merging.

If your lists don't cointain really big data (more than millions), the performance really doesn't matter.

Upvotes: 0

Related Questions