Linked List Insertion in the middle

Question

Node InsertNth(Node head, int data, int position) {


    Node start,curr,temp;
    start=head;
    curr=start;
    if(start==null)
        {
        temp=new Node();
        temp.data=data;
        temp.next=null;
        return head;
    }
    else if(position==0)
        {
        temp=new Node();
        temp.data=data;
        temp.next=start;
        return head;
    }
    else
        {
        for(int i=0;i<position;i++)
            {
            System.out.println("i:"+i);
            curr=start;
            start=start.next;
        }
        temp=new Node();
        temp.data=data;
        curr.next=temp;
        temp.next=start;
        return head;
    } 
}

In the above code I printed the value of "i" in the for-loop. In the console I am getting the output as

i:0
i:0
i:1
i:0
i:1
i:2
i:3

And

Exception in thread "main" java.lang.NullPointerException
    at Node.InsertNth(Solution.java:49)
    at Solution.main(Solution.java:88)

Why is "i" not incrementing properly? If it does work well then I can perform insertion in middle.

Answer 1

First, why is return head; in your first two cases? temp is the new head of the list and should be returned instead.

Second, your loop is correct. However, Hackerrank runs multiple test cases. I typed up a solution and inserted newlines at the beginning of the method call. You simply have three test cases executing.

i: 0

i: 0
i: 1

i: 0
i: 1
i: 2
i: 3

---

Improvements

1. You'll always have to create a new Node, so refactor that to make your code cleaner.

2. You don't need the start == null check, since you'll just append the old head (which may be null) to the end whenever position == 0.

With the improvements inserted:

Node InsertNth(Node head, int data, int position) {
    Node temp = new Node();
    temp.data = data;
    Node start = head;
    Node curr = start;
    if (position == 0)
    {
        temp.next = start;
        return temp;
    } 
    else
    {
        for(int i = 0; i < position; i++)
        {
            curr=start;
            start=start.next;
        }
        curr.next=temp;
        temp.next=start;
        return head;
    } 
}