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
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; }
srinusreenivas [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; }
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;
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.
anirudh12n96 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?
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 :)
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;
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; }
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.
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.
dl_123 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 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 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 Thanks for pointing out. I didn't get that idea. 😅
krmld 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 please explain....how you are adding cur to head
davidwihl 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 Amazing code thanks
jeremyHenry 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 Add JavaScript support
ada_peiy 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 [deleted]DanHaggard 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 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 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****
gindij 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 it should ignore then
ayushoriginal Code such that If anything goes beyond the last position then the element is inserted at the last possible position
motox2 position will always be between 0 and the number of the elements in the list (inclusive).
AllisonP I added a null check in my loop to not advance my iterator to the next element if it evaluated to null.
Sort 503 Discussions, By:
Please Login in order to post a comment