I am trying to merge 2 sorted LinkedList into one sorted List , but getting NullPointerException?

Question

Here is the code i have written, it works fine until i get to the loop, it crashes showing NullPointerException

Looks like i am missing something very basic here.. but when i run the algorithm on pen & paper i don't see any problem at all.

What am i doing wrong please help !

package lesson.datastructure;

public class MergeSort {

    public static Node getSortedNode1(){
        Node n1=new Node();
        n1.value=2;
        Node n2=new Node();
        n2.value=76;
        Node n3=new Node();
        n3.value=98;
        n1.next=n2;
        n2.next=n3;
        n3.next=null;
        return n1;
    }
    public static Node getSortedNode2(){
        Node n1=new Node();
        n1.value=23;
        Node n2=new Node();
        n2.value=65;
        Node n3=new Node();
        n3.value=87;
        n1.next=n2;
        n2.next=n3;
        n3.next=null;
        return n1;
    }
    public static void printNode(Node head,String name){

        System.out.println(name);
        while(head!=null){
            System.out.print(head.value+"->");
            head=head.next;
        }
        System.out.println("\n\n");
    }

    /* Main method ignore all other methods */
    public static void main(String[] args){

        Node head1,head2;
        head1=getSortedNode1();
        head2=getSortedNode2();

        printNode(head1, "List 1");
        printNode(head2, "List 2");

        Node sortedMergedList=null;

        if(head1.value<head2.value){
            Node nextNode=head1.next;
            Node isolatedNode=null;
            isolatedNode=head1;
            isolatedNode.next=sortedMergedList;
            sortedMergedList=isolatedNode;
            head1=nextNode;
        }
        else
        {
            Node nextNode=head2.next;
            Node isolatedNode=null;
            isolatedNode=head2;
            isolatedNode.next=sortedMergedList;
            sortedMergedList=isolatedNode;
            head2=nextNode;
        }


        while(head1!=null || head2!=null){
       //Null pointer here while accessing head1 or head2
            if(head1.value<head2.value){
                Node nextNode=head1.next;
                Node isolatedNode=null;
                isolatedNode=head1;
                isolatedNode.next=sortedMergedList;
                sortedMergedList=isolatedNode;
                head1=nextNode;
            }
            else
            {
                Node nextNode=head2.next;
                Node isolatedNode=null;
                isolatedNode=head2;
                isolatedNode.next=sortedMergedList;
                sortedMergedList=isolatedNode;
                head2=nextNode;
            }

        }
            printNode(sortedMergedList, "merged sorted list");

    }


    }

@rD. updated the answer showing the area of error, what am i doing wrong ? — Sujal Mandal, Aug 22 '16 at 03:24
Here, OP is missing the basic concept of `merge` sort algorithm. There is 1 more condition after while loop where we insert all the values from `non-null` list to resultant `merged list` — Raman Sahasi, Aug 22 '16 at 03:36
@rD. That would be one way to do it, but it replicates code. The [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself) principle suggests that simply adding null checks to the `if` statement will have the same effect, *without* repeating code. — Andreas, Aug 22 '16 at 03:38
At the second Linket list: > 23->65->87 it will assign `Node nextNode=head2.next` when compare `87` and `98`, so `nextNode=null`, then enter while loop, because `head1!=null, head2==null`, at last execute `head1.value — Tangoo, Aug 22 '16 at 03:42
@rd. you are right i forgot that condition where one of the list is exhausted ! So stupid of me, & if any of you wants to add an answer i will accept it. — Sujal Mandal, Aug 22 '16 at 05:42
@SujalMandal It has been marked as duplicate (*I wonder why*) so no new answers would be accepted for this question. — Raman Sahasi, Aug 22 '16 at 05:49
@rD. shame.. SO should have a feature where they put "duplicate" questions as "variations" because so many duplicate questions are not exactly duplicate. Anyways i am really thankful i was able to fix it after learning the missing concept you talked about. — Sujal Mandal, Aug 22 '16 at 06:03

Zhaode Wang · Answer 1 · 2016-08-22T03:49:18.283

0

I think the conditions that select head should be value and isNull, so the isNull condition should be added likes below.

if(head1!=null&&(head2==null||head1.value<head2.value)){

edited Aug 22 '16 at 03:49

answered Aug 22 '16 at 03:28

Zhaode Wang

1
2

Has to be `||`, since you need all values from *both* lists. It's the `head1.value – Andreas Aug 22 '16 at 03:33
Sorry, i didn't read all the code, now the answer is update. – Zhaode Wang Aug 22 '16 at 03:47

I am trying to merge 2 sorted LinkedList into one sorted List , but getting NullPointerException?

1 Answers1