Inserting a node in a pre sorted linked list

Question

I have been going through the Linkedlist problems on hacker rank and I am currently solving the question which will ask you to insert a node in a sorted doubly linkedlist.

This is my logic I wrote in Java

Node SortedInsert(Node head,int data) {

    Node newNode = new Node();
    Node temp = head;
    newNode.data = data;
    newNode.next = null;
    newNode.prev = null;

    if(head == null){
        head = newNode;
    }else{
        while(data > temp.data && temp.next != null){
            temp = temp.next;
        }
        if(temp == head){
            newNode.next = temp;
            temp.prev = newNode;
            head = newNode;
        }else if(data > temp.data){
            newNode.prev = temp;
            temp.next = newNode;
        }else{
            newNode.prev = temp.prev;
            newNode.next = temp;
            temp.prev.next = newNode;
            temp.prev = newNode;
        }

    }

  return head;
}

This is the error I get.

Your Output (stdout)
Wrong Answer!
Some possible errors:
1. You returned a NULL value from the function. 
2. There is a problem with your logic
Wrong Answer!
Some possible errors:
1. You returned a NULL value from the function. 
2. There is a problem with your logic

I have no idea what I did wrong. I really want to know where I went wrong. I know it is easy to find answer online but i think i will learn the best if someone can correct my mistake.

Answer 1

The problem is that you're always inserting the second element in the list before the first element. Consider the following illustration:

Let the linked list is empty initially. Now you follow your algorithm to insert 1. The head == null case is triggered and head points to newNode now.

x<-1->x
   |
  HEAD

Now, you try to insert 2 in the list. You'll see that the while loop ends and temp now points to head, triggering the if condition that follows (if(temp == head)).

x<-1->x
   |
  HEAD, temp

This inserts 2 (incorrectly!) before temp.

x<-2<=>1->x
   |
  HEAD

Swapping the order of the conditions should fix the problem:

    if(data > temp.data) {    // First, check if you need to insert at the end.
        newNode.prev = temp;
        temp.next = newNode;
    } else if(temp == head) { // Then, check if you need to insert before head.
        newNode.next = temp;
        temp.prev = newNode;
        head = newNode;
    } else {                  // Otherwise, insert somewhere in the middle.
        newNode.prev = temp.prev;
        newNode.next = temp;
        temp.prev.next = newNode;
        temp.prev = newNode;
    }