beladiyahardik7 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 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 Well I think in custom input author does not want this
dev_shasif Wasted a lot of my time
DarshakMehta Same here...
rohan_it05 same here
shwetanka99_dipa same here
etayluz 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 [deleted]kau5hik1 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 if (head == NULL) { newNode->next = NULL; head = newNode; return; }
debnathkundu newNode is always having NULL in its next field owing to the constructor mentioned in the class structure.
i.e. if we initialise a new node with data (by passing it as argument), we call the default constructor, which initialises newNode's data as data and newNode's next as NULL
pranjal__g this solution will fail for 1st position.
NandiChaurasiya Here, if you write the below code, its not going inside it, what's the reason: if(head == NULL) cout<<"Head is NULL"<
Ashish110110 newNode->next = currentNode->next; currentNode->next = newNode;
please explain
akshita_ch please explain currentNode->next=newNode;
pasoevi You aren't
freeing the dynamically allocated newNode and alsoheadwhen position is0.murali_marimeka1 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 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; }
tanyacoding25 C++ solution SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) {
SinglyLinkedListNode *t=new SinglyLinkedListNode(data); SinglyLinkedListNode *p=head;t->data=data; p=head; for(int i=0;i<position-1;i++){ p=p->next; } t->next=p->next; p->next=t;return head; }
adelin_ghanayem I think next time it is good to clarify things like this !
arpitmantri7501 [deleted]arpitmantri7501 @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 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 ofhead==nullcondition as we would expect.
gnazaryan 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 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 Did it pass all the test cases?.I have implemented similar logic and it is hwoing Run time error.
sarveshbhagat 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 [deleted]deekshith565 [deleted]deekshith565 if(head==null){ head=n; return head; } This is not required.
miguelangel_par1 thank you, it works!!!
ltocode 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 can you please explain the above code ? I didn't get it fully.
zmingxie 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 what does the "newNode.next = cur.next;" line do?
ds1354586 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 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 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 You are correct. I think they're only printing non-duplicate values.
vivekranjan92 @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 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 Thanks man :)
arpitmalviya996 [deleted]
duyhung285 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 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 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 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 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 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 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 Can you explain your code ?
sveolon 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 Thanks mate :) I completed this challenge but it always better to know diff way solving problem .
sunnyhong93 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 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 Elegant !!
milad 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 i don't understand
marshal4world [deleted]marshal4world [deleted]marshal4world [deleted]
153J1A0575 thank u
micro_zhu 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 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 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 head.next = InsertNth(head.next,data,position-1);
Why you used head.next why not only head?
Thelaughinglama 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 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 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 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.
mrigank2303239 This is the improved code
def insertNodeAtPosition(head, data, position): n=head if position==0: head=SinglyLinkedListNode(data) head.next=n else: for i in range(position-1): n=n.next n_next=n.next n.next=SinglyLinkedListNode(data) n.next.next=n_next return head
maqsudinamdar7 Can someone explain me this code?
renato314159 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 [deleted]
amaljanan333 static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode head, int data, int position) {
SinglyLinkedListNode new_node = new SinglyLinkedListNode(data); SinglyLinkedListNode cnode = head; while(--position > 0) { cnode = cnode.next; } new_node.next = cnode.next; cnode.next = new_node; return head; }
varunrisbud 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 SAME PROBLEM
adelin_ghanayem I've already wasted like 2 hours !!!! by trying to solve it myself !!!
karid55 I thought i was the only one having issues until i read this i think the assignment instructions were poorly written
cameronellis711 Absolutely agree. This is a terrible problem
Hunter_ 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 there is something wrong with the test case. What did you do to pass the test ?
Hunter_ 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_ 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 I have this same issue, the head is 2 right from the beggining even though there is no 2 passed as input yet.
atique 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 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 your code is wrong
atique your comment is useless without some details
lauryndbrown This problem statement is pretty horrible. What exactly is the input format?
rubenavazquez 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.
Sort 726 Discussions, By:
Please Login in order to post a comment