Anand Tyagi Anand Tyagi - 25 days ago 7
Java Question

Why doesn't he following code works in inserting node at a specific postion in a Linked List?

Please take a look at the following code and let me know what's wrong with it? I'm trying to insert a node at a given specific position in a linked list. We need to return the reference to the head node after inserting it.

Node InsertNth(Node head, int data, int position) {
Node newNode = new Node();
newNode.data = data;

if(head==null){
newNode.next = head;
return newNode;
}
Node first = head;

while(position > 0 && head.next!=null){
head = head.next;
position -= 1;
}

newNode.next = head;
head = newNode;
return first;

}

Answer

Yeah, there is something wrong. After the while loop, you are trying to insert newNode BEFORE head, but this does not work. The line head=newNode; is useless.

Either you need another pointer to point to the node before head, so that you can insert newNode between these two pointers, or you need to stop the while loop one step before, and insert newNode AFTER head. Here is the second solution:

 while(position > 1 && head.next!=null){ //0 is replaced by 1 here
    head = head.next;
    position -= 1;
}

newNode.next = head.next;
head.next = newNode;
return first;

[EDIT]

In this solution, you need to handle the special case when position equals 0 by adding the following code just before the while loop:

if(position==0) {
    newNode.next = head.next;
    return newNode;
}
Comments