## Insert a node at a specific position in a linked list

- HB
beladiyahardik7 + 8 comments Hey guys is there is any problem in test case. I think there is problem in the 2 4 because for that atleast we require 3 node . and if i am correct then please correct the input as soon as possible

- JH
hejohnny + 14 comments Solution below in Java. The author probably wanted position paramaters exceeding the List size to be added to the end of the List.

Node InsertNth(Node head, int data, int position) { //Will Need to Return Head Node Node trackedHeadNode = head; Node nodeToInsert = new Node(); nodeToInsert.data = data; //Empty List - Returned newly created node or null if (head==null){return nodeToInsert;} //Inserting a Node ahead of the List if (position == 0){nodeToInsert.next = head; return nodeToInsert;} //Traverse the Singly Linked List to 1 Position Prior //Stop traversing if you reached the end of the List int currPosition = 0; while (currPosition < position -1 && head.next != null){ head = head.next; currPosition++; } //Inserting a Node in-between a List or at the end of of a List Node nodeAtPosition = head.next; head.next = nodeToInsert; head = head.next; head.next = nodeAtPosition; return trackedHeadNode; }

- D
dev_shasif + 0 comments Well I think in custom input author does not want this

- D
dev_shasif + 1 comment Wasted a lot of my time

DarshakMehta + 1 comment Same here...

- RS
rohan_it05 + 0 comments same here

etayluz + 5 comments C solution:

`Node* InsertNth(Node *head, int data, int position) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; if (head == NULL) { return newNode; } if (position == 0) { newNode->next = head; return newNode; } Node *currentNode = head; while (position - 1 > 0) { currentNode = currentNode->next; position--; } newNode->next = currentNode->next; currentNode->next = newNode; return head; }`

srinusreenivas + 0 comments [deleted]- K
kau5hik1 + 1 comment when head is NULL you need to make newNode->next = NULL, else the linked list wouldn't end with a NULL.

if (head == NULL) { newNode->next = NULL; return newNode; }

- SP
saryu21090 + 0 comments if (head == NULL) { newNode->next = NULL; head = newNode; return; }

pranjal__g + 0 comments this solution will fail for 1st position.

- NC
NandiChaurasiya + 0 comments Here, if you write the below code, its not going inside it, what's the reason: if(head == NULL) cout<<"Head is NULL"<

- A
Ashish110110 + 0 comments newNode->next = currentNode->next; currentNode->next = newNode;

please explain

adelin_ghanayem + 0 comments I think next time it is good to clarify things like this !

arpitmantri7501 + 0 comments [deleted]arpitmantri7501 + 0 comments @hejohnny : you dont need to check "head.next != null" in while loop as it is mentioned in the question that position will be in between 0 and the number of nodes of the linked list provided.

- PS
psundars + 0 comments In addition, the head may not be null the first time this method is called. For the given test case, the 3 uses

`If(position==0)`

condition instead of`head==null`

condition as we would expect. gnazaryan + 1 comment Hey, I am Greg :) I was looking through your code and I see the implementation accepts duplicate values, at least my local test printed duplicates.

It is really amasing, according to test case and expected output no duplicates must be contained, but actually your code passes the test :)

I have just posted also my solution which is somehow wrong but only for last entrie magically, because on my local environment it runs correctly....

lzhang800 + 2 comments Here is a different solution in Java. Took me awhile to figure out the different test secarnios. We should keep track of the element before the given position so that we can modify the next element.

`Node InsertNth(Node head, int data, int position) { Node newNode = new Node(); Node header = head; // scenario when head is null if ( head == null) { newNode.data = data; return newNode; } newNode.data = data; // scenario when we want to insert in the first element on the list if (position == 0) { newNode.next = head; header = newNode; return header; } // insert somewhere else 1th, 2th, 3th, etc... // should stop the element before the position to keep track of next element and assign to a new element for (int i=1; i < position && head.next !=null; i++) { head = head.next; } if (head.next != null) { newNode.next = head.next; head.next = newNode; } else { head.next = newNode; } return header; }`

- PS
priyaSin + 1 comment Did it pass all the test cases?.I have implemented similar logic and it is hwoing Run time error.

- SB
sarveshbhagat + 3 comments Much cleaner code :

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

`Node n = new Node(); n.data=data; if(head==null){ head=n; return head; } if(position==0){ n.next=head; return n; } else { int ctr=0; Node temp1 = head; while(ctr < position-1 && temp1.next!=null){ temp1=temp1.next; ctr++; } Node temp2= temp1.next; temp1.next=n; // better temp1's pointer is assinged n; n.next=temp2; // n's pointer is assinged temp2 return head; }`

}

- S
SatyanarayanSP + 0 comments [deleted] - DR
deekshith565 + 0 comments [deleted] - DR
deekshith565 + 0 comments if(head==null){ head=n; return head; } This is not required.

- AD
anirudh12n96 + 0 comments Even I had a similar idea. Did your code pass all the test cases?

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

`Node newNode = new Node(); newNode.data = data; int count = 1; if(position == 1) { if(head == null) { head = newNode; newNode.next = null; } else { newNode.next = head; head = newNode; } } else { Node current = head; while(count<position - 1 || current.next!=null) { current = current.next; count++; } newNode.next = current.next; current.next = newNode; } return head;`

}

ghoshamitabha090 + 0 comments can you please explain the above code ? I didn't get it fully.

- Z
zmingxie + 1 comment My idea is similar:

Node InsertNth(Node head, int data, int position) { Node newNode = new Node(); newNode.data = data; // Special case: insert in the front if(position == 0) { newNode.next = head; return newNode; } // Other cases: found the node at position - 1 // newNode.next = Node(position -1).next // Update Node(position -1).next = newNode Node cur = head; int curPos = 0; while(curPos != position - 1) { cur = cur.next; curPos += 1; } newNode.next = cur.next; cur.next = newNode; return head; }

- F
folasadeajayi + 0 comments what does the "newNode.next = cur.next;" line do?

shantanuraje + 1 comment this solution works..test it after a long time of trying to solve this. i still have a doubt.. The head node at first has a 2 so it is 2-null The sequence of operation then is given as.. 3 0, 3-2-null 5 1, 3-5-2-null 4 2, 3-5-4-2-null 2 3, 3-5-4-2-2-null 10 1, 3-10-5-4-2-2-null (should this be the result instead of 3-10-5-4-2?) correct me if i am wrong! Thank you.

DimitarK + 0 comments You are correct. I think they're only printing non-duplicate values.

vivekranjan92 + 0 comments @hejohnny Here, inside the while loop you have used position but you have not defined it. Won't that be a problem for compiler?

NightRaven97 + 1 comment Here's my solution in Java. I missed the fact that head could be null. Thanks to you! But the traversal part in your solution seems complex, so I thought I could post mine.

Node InsertNth(Node head, int data, int position) { Node newNode = new Node(); newNode.data = data; if(head == null) return newNode; else if(position == 0) { newNode.next = head; return newNode; } Node currNode = head; for(int i=0; i<position-1; i++) { currNode = currNode.next; } newNode.next = currNode.next; currNode.next = newNode; return head; }

vivekranjan92 + 0 comments Thanks man :)

davekartik24 + 0 comments Why not simply we can write the below:

//Inserting a Node in-between a List or at the end of of a List nodeToInsert.next = head.next; head.next = nodeToInsert;

`return trackedHeadNode;`

ashokdey + 1 comment Here is my code in C++ that passed all the tests !

Node* InsertNth(Node *head, int data, int position) { Node *temp = head; if (head == nullptr) { // create a new node Node *mynode = new Node; mynode->data = data; mynode->next = nullptr; head = mynode; return head; } else { //count the number of nodes int count = 0; while (temp != nullptr) { ++count; temp = temp->next; } if (position == 0) { Node *mynode = new Node; mynode->data = data; mynode->next = head; head = mynode; return head; } else if (position >= count ) { // got to the last node temp = head; while (temp->next != nullptr) { temp = temp->next; } Node *mynode = new Node; mynode->data = data; mynode->next = nullptr; temp->next = mynode; return head; } else { temp = head; int pos = 0; while (temp->next != nullptr && pos < position-1) { ++pos; temp = temp->next; } Node *mynode = new Node; mynode->data = data; mynode->next = temp->next; temp->next = mynode; return head; } } }

saeven + 2 comments Much too long, you can simplify this by not iterating when you don't need to.

Node newNode = new Node(); newNode.data = data; Node current = head; if( position == 0 ){ newNode.next = head; return newNode; } int counter = 0; while( ++counter < position ){ current = current.next; } newNode.next = current.next; current.next = newNode; return head;

- VC
sveolon + 5 comments Why so long?

Node** p = &head; for(int i = 0; i < position; ++i) p = &(*p)->next; *p = new Node {data, *p}; return head;

arp_pathak888 + 1 comment Can you explain your code ?

- VC
sveolon + 1 comment Well, yes. I am using p as an iterator. Since "head" is a pointer to Node (type is Node*), type of p will be Node** (pointer to pointer to Node). &head is the address of the variable storing beginning of the list. Thus,

Node** p = &head;

To get to the correct position, I need to move my pointer "position" times, so I am using a cycle. Inside of the cycle I assign p to the value of the next pointer:

p = &(*p)->next;

Here, p is of type Node**, so I dereference it by calling * p (now our type is Node*, and this is just a Node pointer). (*p)->next is "the next element from the node pointed by p". Finally, I use & to get address of the node we are moving to.

*p = new Node {data, *p};

Here in the right side is a new Node created, having data in value field and content of current "p" iterator in next. I am using curly brace initializer for simplicity. On the left side I assign the newly created Node to the list element currently at the "position", so it becomes inserted into the list (current p were assigned to new node's next as a part of initialization).

So here it is. I hope this explanation helps.

arp_pathak888 + 0 comments Thanks mate :) I completed this challenge but it always better to know diff way solving problem .

sunnyhong93 + 0 comments This is how I did in C++.

Node* InsertNth(Node *head, int data, int position) { Node *root; root= head; Node *temp = new Node(); temp->data=data; if (position<0){return NULL; } else if (position==0){ temp->next= head; return temp; }else{ while(position-1>0){ position--; head= head->next; } temp->next= head->next; head->next= temp; return root; } }

- Y
yenWu + 0 comments That's what I though. But my implementation is in C.

Node *nodp = (Node *) malloc(sizeof(Node)); nodp->data = data; Node** dp = &head; while (0 < position--) dp = &(*dp)->next; nodp->next = *dp; *dp = nodp; return head;

iam_ghanshyam + 0 comments Elegant !!

milad + 0 comments Agreed in fact something like what you are sayign is the most elegant solution, I thought mine was :/

Node n = new Node(); n.data = data; Node cur = head; Node prev = null; int i = 0; while (i < position) { prev = cur; cur = cur.next; i++; // will crash if input head = null and pos > 0 // we assume no such inputs } n.next = cur; if (prev != null) { prev.next = n; return head; } return n;

- RG
ritulgoti + 3 comments i don't understand

marshal4world + 0 comments [deleted]marshal4world + 0 comments [deleted]marshal4world + 0 comments [deleted]

- NG
- VH
153J1A0575 + 0 comments thank u

- JZ
micro_zhu + 0 comments java recursive function

Node InsertNth(Node head, int data, int position) { if(position>0) { head.next = InsertNth(head.next, data, position-1); return head; }

`Node newNode = new Node(); newNode.data = data; newNode.next = head; return newNode;`

}

- IS
ishanshekhar0502 + 0 comments Node* InsertNth(Node *head, int data, int position) { struct Node *i,

*newn; int count=0; newn=(struct Node*)malloc(sizeof(struct Node)); newn->data=data; if(!head) { newn->next=NULL; head=newn;`} else if(position==0){ newn->next=head; head=newn; } else{ i=head; while(i->next!=NULL&&count<(position-1)){ i=i->next; count++; } newn->next=i->next; i->next=newn;`

} return head; }

- SS
ssubashs + 0 comments java solution with recursion seems easier.

if(head == null){ Node x = new Node(); x.data = data; return x; } if(position ==0){ Node x = new Node(); x.data = data; if(head !=null){ x.next = head; } return x; }else{ head.next = InsertNth(head.next,data,position-1); return head; }

varunrisbud + 4 comments This is NOT a properly designed test case. Output is getting swapped when linked list starts with 2. Dont waste your time on this question.

pkssaini94 + 0 comments SAME PROBLEM

adelin_ghanayem + 0 comments I've already wasted like 2 hours !!!! by trying to solve it myself !!!

karid55 + 0 comments I thought i was the only one having issues until i read this i think the assignment instructions were poorly written

- C
cameronellis711 + 0 comments Absolutely agree. This is a terrible problem

Hunter_ + 2 comments Either the test case that the author has included is broken or they have incorrectly described the test data and how the function should work. I was only able to pass it by including some special case code to get rid of a head node with data=2 and insert a tail node with a data=2. This challenge should be deleted until the author can fix the issues.

- RC
rafael_carrasco1 + 2 comments there is something wrong with the test case. What did you do to pass the test ?

Hunter_ + 0 comments I just hacked in a check at the beginning:

if (head->data == 2) { delete head; head = nullptr; }

And then another special case hack to insert a node containing 2 after the 4.

- DB
drover_ + 0 comments There is nothing wrong with the test case. Hunter_ likely had an off by one error.

Edit: Just FYI, the "hack" he used wouldn't work against virtually any other test case. Check the section of code where you iterate. There is likely an off by one error there if your output is incorrectly ordered.

- A
aprobst1 + 0 comments I have this same issue, the head is 2 right from the beggining even though there is no 2 passed as input yet.

atique + 1 comment There is a flaw in the design of the problem's INPUT/OUTPUT.

- It should give head as NULL which it does not.
- There is an extra number expected at the end of the linked list

This is accepted code,

`Node* InsertNth(Node *head, int data, int position) { if (position == 0) return head = new Node({data, new Node({2, NULL})}); Node* root = head; while (root->next && --position) root = root->next; root->next = new Node({data, root->next}); return head; }`

And, this is what accepted code should look like,

`Node* InsertNth(Node *head, int data, int position) { if (head == NULL) return head = new Node({data, NULL}); if (position == 0) return head = new Node({data, head->next}); // strict checking as my habit if (position < 0) return NULL; Node* root = head; while (root->next && --position) root = root->next; root->next = new Node({data, root->next}); return head; }`

- T
thiago_hirai + 0 comments I'm fairly certain that the test runner for C++ is broken. I wrote a nearly identical solution in Java and it passed, no problem.

- DL
dl_123 + 1 comment Just to help clear things up in case anyone is confused like I was. Like others have hinted at, the initial '2' value is important. Even though it shouldn't be necessary for the purposes of this test, for the test to pass, the first '2' should ideally stay in your linked list and your algorithm would just keep that first '2' at the tail as it inserts new values. The code seems to expect the '2' to be at the end so I guess the test omits the last item of your linked list when printing and comparing the results at the end of each test.

I tried to be clever and remove the 2 at the start and this didn't work, as my algorithm ended up producing this for Test Case 0:

3 -> 10 -> 5 -> 4 -> 2

The test will print it out as: 31054 (notice the last value is missing)

Therefore you should have your algorithm produce this (for Test Case 0):

3 -> 10 -> 5 -> 4 -> 2 -> 2

And the test will print it out as: 310542

- CC
chaitanya_14795 + 1 comment Thanks your explanation cleared my doubt about how the test case is working.

Here is the python version of it if anyone is interested.

def InsertNth(head, data, position): if not position == 0: _head = head current_position = 1 while(position - current_position>0): _head = _head.next current_position+=1 if _head.next is None: _head.next = Node(data,None) return head else: prev = _head.next _head.next = Node(data,prev) return head else: return Node(data,head)

timnosov + 2 comments your logic is unnessessarily complicated. Here's a better python3 version

def InsertNth(head, data, position): if position == 0: node_to_isert = Node(data=data, next_node=head) return node_to_isert node = head for i in range(position-1): node = node.next node_to_isert = Node(data=data, next_node=node.next) node.next = node_to_isert return head

- CC
chaitanya_14795 + 0 comments Thanks for pointing out. I didn't get that idea. ðŸ˜…

- S
krmld + 3 comments May be test cases are changed, following code passes all test cases:

def InsertNth(head, data, position): if position == 0: head = Node(data, head) else: cur = head for _ in range(position-1): cur = cur.next cur.next = Node(data, cur.next) return head

- TV
veerpassion12 + 0 comments please explain....how you are adding cur to head

- DW
davidwihl + 0 comments Another flavor, with an extra short circuit check and a while loop. This handles pathological cases better (like position > length of list):

def InsertNth(head,data,position): if head is None or position == 0: return Node(data,head) else: cur_pos = 1 cur_node = head while cur_node.next and cur_pos < position: cur_node = cur_node.next cur_pos += 1 cur_node.next = Node(data,cur_node.next) return head

- JD
jae_duk_seo + 0 comments Amazing code thanks

- LB
lauryndbrown + 1 comment This problem statement is pretty horrible. What exactly is the input format?

- RV
rubenavazquez + 0 comments It looks like from the Input box, 5 is the number of inputs and you have the position on the right side and the value to add on the left.

- JH
jeremyHenry + 0 comments This test is garbage. The solution that passes here will not pass with the same supposed inputs in REAL C++. Please re-write to teach users the correct way to write an insert function.

vovchuck_bogdan + 0 comments Add JavaScript support

- AP
ada_peiy + 3 comments Here is my python solution. It passes all the test cases

def InsertNth(head, data, position): if head is None: # position must be 0 return Node(data, None) if position == 0: return Node(data, head) prevNode = head for _ in range(position-1): prevNode = prevNode.next prevNode.next = Node(data, prevNode.next) return head

- D
DanHaggard + 0 comments [deleted] - D
DanHaggard + 0 comments Slight variation which has the virtue of having fewer conditionals:

def InsertNth(head, data, position): if position == 0: return Node(data=data, next_node=head) else: curr_node = head for _ in range(position): prev_node = curr_node curr_node = curr_node.next prev_node.next = Node(data=data, next_node=curr_node) return head

AffineStructure + 0 comments Here is my version.

def InsertNth(head, data, position): if head is None or position <= 0: return Node(data, head) else: probe = head while position > 1 and probe.next is not None: probe = probe.next position -= 1 probe.next = Node(data, probe.next) return head

- G
gindij + 3 comments Have any of these posts been resolved? I think their test case might have a mistake in it (they ask us to insert at position 4 when we have only added 3 to the list).

megido + 0 comments it should ignore then

ayushoriginal + 1 comment Code such that If anything goes beyond the last position then the element is inserted at the last possible position

motox2 + 0 comments position will always be between 0 and the number of the elements in the list (inclusive).

AllisonP + 0 comments I added a null check in my loop to not advance my iterator to the next element if it evaluated to null.

Sort 478 Discussions, By:

Please Login in order to post a comment