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

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

beladiyahardik7 + 9 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

hejohnny + 16 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; }

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

dev_shasif + 1 comment Wasted a lot of my time

DarshakMehta + 1 comment Same here...

rohan_it05 + 1 comment same here

shwetanka99_dipa + 0 comments same here

etayluz + 9 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; }`

srinivaschkdhi + 0 comments [deleted]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; }

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

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

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"<

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

please explain

akshita_ch + 0 comments please explain currentNode->next=newNode;

pasoevi + 0 comments You aren't

`free`

ing the dynamically allocated newNode and also`head`

when position is`0`

.murali_marimeka1 + 0 comments Added belts and braces

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(currentNode->next != NuLL && position - 1 > 0) { currentNode = currentNode->next; position--; } if(currentNode ->next == NULL) { cout << "No element at position "<< position << endl; return; } newNode->next = currentNode->next; currentNode->next = newNode; return head;`

}

pulkitraj131 + 0 comments In c++

SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) { SinglyLinkedListNode *temp=new SinglyLinkedListNode(data); SinglyLinkedListNode *nh= head; for(int i=0;i<position-1;i++) { nh=nh->next; } SinglyLinkedListNode *t; t=nh->next ; nh->next=temp; temp->next=t; return head; }

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.

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; }`

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

sarveshbhagat + 4 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; }`

}

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

miguelangel_par1 + 0 comments thank you, it works!!!

ltocode + 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.

zmingxie + 2 comments 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; }

folasadeajayi + 1 comment what does the "newNode.next = cur.next;" line do?

ds1354586 + 0 comments it shifts the pointer of new node to the actual next node of the node chain in the linked list.after that we just need to change the next to new node

jinwangabriel + 0 comments When the input's head is empty and position > 0, I think you will have a problem at "cur = cur.next" inside the while.

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 + 3 comments 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 :)

arpitmalviya996 + 0 comments [deleted]duyhung285 + 0 comments The problem here is you add a new node to the linked list but never update the head or the tail when needed. For example when the passed head is null (empty list). You just return the newNode. The head supposes to reference to the newNode but you never do it here. You cannot do it because you do not have access to the head here. If you inserted at the last position of a not empty linked list, then you would update the tail as well but you cannot do it. You do not have access to the tail.

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;`

grishabh282 + 0 comments My Solution

SinglyLinkedListNode n=new SinglyLinkedListNode(data);

`SinglyLinkedListNode node=head; while(position!=1 && node.next!=null) { node=node.next; position--; } SinglyLinkedListNode temp=node.next; node.next=n; n.next=temp; return head;`

BaskaranR + 0 comments Another node assignment is not required;

static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode head, int data, int position) {

`SinglyLinkedListNode headNode = head; SinglyLinkedListNode newNode = new SinglyLinkedListNode(data); int pos = 0; while(headNode.next != null && pos < position - 1){ headNode = headNode.next; pos++; } SinglyLinkedListNode nodeAtPosition = headNode.next; headNode.next = newNode; newNode.next = nodeAtPosition; return head; }`

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;

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 ?

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; } }

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;

ritulgoti + 3 comments i don't understand

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

153J1A0575 + 0 comments thank u

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;`

}

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; }

ssubashs + 1 comment 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; }

kailashuniyal04 + 1 comment head.next = InsertNth(head.next,data,position-1);

`Why you used head.next why not only head?`

Thelaughinglama + 0 comments Head needs to be updated and point where the next node is pointing.The whole idea behind using recursion is to make the problem smaller and reaching the base case.To make the problem smaller we will shift head by 1 each time and check for base case.We will do it till we reach base case execute that and return.

eduasinco + 3 comments Thank you!, my python version:

def insertNodeAtPosition(head, data, position): n = head for _ in range(position - 1): n = n.next n_next = n.next n.next = SinglyLinkedListNode(data) n.next.next = n_next return head

milesb + 1 comment I got almost the same answer. There is a small improvement to be had.

def insertNodeAtPosition(head, data, position): n = head for _ in range(position - 1): n = n.next n_next = n.next n.next = SinglyLinkedListNode(data) n.next.next = n_next return head

alvaroSanchez + 0 comments Both are wrong IMHO. 'position' variable could take value 0 according to the constraints of the problem. That means that you have to insert the data in the head of the list. But in your code you are inserting in position 1 when the 'position' value is 0. Your code behaves the same when 'position' is 1 and when 'position' is 0.

maqsudinamdar7 + 1 comment Can someone explain me this code?

renato314159 + 0 comments I will try my best.

`def insertNodeAtPosition(head, data, position): n = head #set variable n to equal head for _ in range(position - 1): n = n.next #loop thru llist until you get to desired position n_next = n.next #set variable n_next to equal the next node n.next = SinglyLinkedListNode(data) #set the next position as the new number n.next.next = n_next #and the one after that as what used to be n.next return head`

tejaswini_giris1 + 0 comments [deleted]

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

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.

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.

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.

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 + 2 comments 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; }`

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.

shiva1996_sc + 1 comment your code is wrong

atique + 0 comments your comment is useless without some details

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

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.

mc_teo + 1 comment Python 2 support seems to be broken:

File "solution.py", line 8 from __future__ import print_function SyntaxError: from __future__ imports must occur at the beginning of the file

scaflowen + 0 comments It's definetely broken.

Take your code and paste it in the python 3 template. If it's correct it will run fine there.

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

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 + 3 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

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

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

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

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

jae_duk_seo + 0 comments Amazing code thanks

ngmjr + 0 comments Without the need to check for the 0th position case:

`def insertNodeAtPosition(head, data, position): # Null case if head is None: return SinglyLinkedListNode(data) cur = head for _ in range(position - 1): cur = cur.next cur.next, cur.next.next = SinglyLinkedListNode(data), cur.next return head`

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

ada_peiy + 4 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

DanHaggard + 0 comments [deleted]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

vilasini_b2015 + 0 comments how to resolve this?

Traceback (most recent call last): File "solution.py", line 77, in llist_head = insertNodeAtPosition(llist.head, data, position) File "solution.py", line 58, in insertNodeAtPosition prevNode.next = SinglyLinkedListNode(data, prevNode.next)

TypeError:**init**() takes 2 positional arguments but 3 were given****

Sort 689 Discussions, By:

Please Login in order to post a comment