Merging two linked list into new one java

Question

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

`while(Head2!=null || Head1!=null)` -> `while(Head2!=null && Head1!=null)`. — David Pérez Cabrera, Sep 10 '16 at 08:22

score 1 · Answer 1 · edited May 23 '17 at 12:08

1

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.

edited May 23 '17 at 12:08

Community

1
1

answered Sep 10 '16 at 09:25

Saurav Sahu

13,038
6
64
79

1

Solved !! :) Thanx – Riya kathil Sep 10 '16 at 13:54

Nikolas Charalambidis · Answer 2 · 2016-09-10T08:53:50.577

0

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.

edited Sep 10 '16 at 08:53

answered Sep 10 '16 at 08:31

Nikolas Charalambidis

40,893
16
117
183

1

The OP asks why his own custom merge function in a custom linked list implementation doesn't work, and your post gives a completely different implementation of the function that doesnt use the OP's linked list. That looks more like a comment to me - not an answer to the question. – Erwin Bolwidt Sep 10 '16 at 08:52
1

Thank you for your reply, but I am trying to implement data structure in java from scratch. – Riya kathil Sep 10 '16 at 09:02

Merging two linked list into new one java

2 Answers2