chetangautam This is wrong. Why do I see input as unsorted, when the problem mentions sorted.
SuperBug It's passing in one node at a time.
e.g.:
2 //two test cases
4 //first test calls your function 4 times
2 1 4 3 //final call should return 1 2 3 4
8 //second test calls your function 8 times
1 2 4 3 7 6 9 10 //final call returns 1 2 3 4 6 7 9 10
ihrushikesh They are calling the SortedInsert method one by one.
e.g. for the input
4
2 1 4 3
the method SortedInsert will be called four times as below,
SortedInsert(head,2) // NULL <--2-->NULL SortedInsert(head,1) // NULL <--1<-->2-->NULL SortedInsert(head,4) // NULL <--1<-->2<-->4-->NULL SortedInsert(head,3) // NULL <--1<-->2<-->3<-->4-->NULL
chetangautam i see. thanks.
alwyns42 The requirement specification is still completely incorrect.
AllisonP If input is given to you in sorted order, then you would only have to insert each element at the end of the list. That wouldn't test your ability to insert items into a sorted list.
An empty list is sorted with respect to itself, as is a one-element list. You must insert one element into this list during each call to the function. The data value given during each call is not ordered because, again, giving you ordered data would only test your ability to insert an element at the tail of a list. Your code must ensure that the insertion point for each element you add to the list doesn't cause the list to become unsorted.
georgekuhl Allison- this problem seems to pass in head as Node(0,None,None) at least for python, which makes it impossible to test for head is None, and completely throws off any attempt to create the correct algorithm. can this be revised to pass head = None?
ikarandeep Having the same issue. Were you able to resolve this?
gs339 Same issue here! Not sure how to implement without testing for None.
cthulhu944 Thought I was going insane. I'm having the same issue in Python 3
mondayrohit How to solve?
calvin_cheng_cc This worked for me (Java):
Node SortedInsert(Node head,int data) { Node n = new Node(); n.data = data; if (head == null) { return n; } else if (data <= head.data) { n.next = head; head.prev = n; return n; } else { Node rest = SortedInsert(head.next, data); head.next = rest; rest.prev = head; return head; } }
etayluz [deleted]etayluz I'm doing the same thing, but I don't like how a new node is being allocated and initialized with every call to sortedInserted() with @calvin_cheng_cc's solution. Those Java guys have no concept of memory management (sorry!). Also, this line above:
else if (data <= head.data) {would be better as
else if (data < head.data) {so that you do the insertion on finding first equality (as opposed to the last equality).
This algorithm is the same one as used for: https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/forum
C solution:
Node* SortedInsert(Node *head,int data) { if(head == NULL) { Node *node = (Node*)malloc(sizeof(Node)); node->data = data; return node; } if(head->data <= data) { head->next = SortedInsert(head->next, data); head->next->prev = head; } else if(head->data > data) { Node *node = (Node*)malloc(sizeof(Node)); node->data = data; node->next = head; node->prev = head->prev; head->prev = node; head = node; } return head; }Atekihcan I have made a small change in your code.
if(head->data <= data) { head->next = SortedInsert(head->next, data); // head->next->prev = head; // The above line is not required as you are already setting that in the else if condition }davidcoler Lets say the next node is null, by the if statement above it only creates the node itself, puts the data in it and returns it. how then if the return is back to that line does the next node know what the previous node is? the
head->next->prev = head;is absolutely necessary unless you want to start from the head again and make sure all the double links are correct. If it goes to the else if statement yes it is superflouous but for the total possibility of all cases being correct this is needed.
terrychu2002 What is the reason for "head = node" in your else if condtion? I am confused because isn't that basically inserting "node" and then having node->next equal to node too?
zhalzel What do you think of this:
Node* makeNode(int data){ Node* newNode = (Node*) malloc(sizeof(Node)); newNode->data = data; newNode->next = 0; newNode->prev = 0; return newNode; } Node* SortedInsert(Node *head,int data){ if (!head) { Node* newNode = makeNode(data); return newNode; } if (data < head->data){ Node* newNode = makeNode(data); newNode->next = head; head->prev = newNode; return newNode; } else{ head->next = SortedInsert(head->next, data); head->next->prev = head; return head; } }
d_negative_zero this recursion will make island of isolated objects due to
Node rest = SortedInsert(head.next, data); Node n = new Node();// hereishansrivastava1 Node* SortedInsert(Node *head,int data) { Node *cur,*p; cur=head->next; Node temp=(Node)malloc(sizeof( Node)); temp->data=data; temp->next=NULL; temp->prev=NULL; if(temp->datadata) { temp->next=head; head->prev=temp; temp->prev=NULL; return temp; } while(cur!=head) { if((temp->data)<(cur->data)) { p=cur->prev; temp->next=cur; cur->prev=temp; p->next=temp; temp->prev=p; return head; } cur=cur->next; } }
a_simpleman awesome!
kapploneon Thanks, with this I understood the recursion very well.
charanacharyah Looks like there's an issue with the Java version. I submitted this,
Node newNode = new Node(); newNode.data = data; if(head == null || head.data >= data){ newNode.next = head; newNode.prev = null; return newNode; } Node current = head; Node prev = null; while(current != null && current.data < data){ prev = current; current = current.next; } Node next = prev.next; newNode.prev = prev; newNode.next = next; if(next != null){ next.prev = newNode; } return head;and I see that the condition head == null is never satisfied. Can someone help?
ghsatpute You have to set both back and next pointers for your nodes. And you have not used
currentnode, use that and set both pointers properly.
priyankakarpe12 One statement is missing: prev.next = newNode;
MakeItHappen [deleted]bhonagiri Node next = current; newNode.prev = prev; newNode.next = next; prev.next = newNode;make this changes it will work...!
raj_yadav29oct please help me my code is not working
Node* SortedInsert(Node *head,int data) { if(head==NULL) { head->data=data; return head; } if(head->next==NULL) { Node *TempNode = (Node*)malloc(sizeof(Node)); TempNode->data=data; TempNode->prev=head; head->next=TempNode; return head; } else { Node* Current=head; Node* previous=NULL; while(Current->data<data&&Current!=NULL) { previous=Current; Current = Current->next; } Node *TempNode = (Node*)malloc(sizeof(Node)); Node* Next=Current; TempNode->data=data; TempNode->prev=previous; TempNode->next=Next; previous->next=TempNode; if(Next != NULL){ Next->prev = TempNode; } } return head; }
dukrishn if(head==NULL) { head->data=data; return head; }
here you are assigning data without allocating memory, it will crash.
AllisonP I successfully solved it in Java. The initial list has one element (a default-constructed Node with a default initial data value of 0) that is stripped out when the custom checker prints your list. That's why
head == nullis never used, but coding for that scenario is still part of the problem.
yaman_batuhan You should have mentioned it.
nipunalways have been scratching my head.. should have mentioned this in bold in problem statement
saxenapawan224 just add condition that previous and next node of the node you add is not null
RodneyShag Java Iterative solution - passes 100% of test cases
From my HackerRank solutions.
Runtime: O(n)
Space Complexity: O(1)Node SortedInsert(Node head, int data) { /* Create Node to insert */ Node newNode = new Node(); newNode.data = data; if (head == null) { // insert in empty list return newNode; } else if (data < head.data) { // insert in front of list newNode.next = head; head.prev = newNode; return newNode; } else { /* Walk list with 2 pointers */ Node n1 = null; Node n2 = head; while (n2 != null && n2.data < data) { n1 = n2; n2 = n2.next; } if (n2 == null) { // insert at end of list n1.next = newNode; newNode.prev = n1; } else { // insert in empty list n1.next = newNode; n2.prev = newNode; newNode.prev = n1; newNode.next = n2; } return head; } }
Let me know if you have any questions.
skyworld8788 I used the same logtic, the only difference is my coding is C++, but got the result of segmentation fault... Could you please help to check why? Thx!
RodneyShag Yes, try posting it as a new thread in a discussion so multiple C++ experts can take a look at it. I'll take a look too.
skyworld8788 [deleted]skyworld8788 Hi rshaghoulian,
I posted the code(c++) here, could you please take a look? Thx!!!!
rujuta_panvalkar Same here. Same logic used with C++ is giving segmentation errors. Did you find any solution to it?
mr746866 What do you think of my solution?
Node SortedInsert(Node head,int data) { Node temp = head; while (temp != null) { if (temp.next == null || temp.next.data >= data) { Node node = new Node(); node.data = data; node.next = temp.next; node.prev = temp; if (temp.next != null) { temp.next.prev = node; } temp.next = node; break; } temp = temp.next; } return head; }
RodneyShag It seems like this code will not work if head is null. No new node would be created in this case.
mr746866 Quoted from the problem: "Your method must return a reference to the head of the same list that was passed to it as a parameter."
Shouldn't we return null if the head is null?
RodneyShag I guess that statement can be interpreted in 2 different ways. I think they would want us to return a 1-element list in that case. I don't think the testcases test for this though.
hammeramr My solution with one pointer - seems like two pointers helps clear a lot of the thought process up :) need to start getting good ideas like that haha
im assuming the space and time complexity are the same
Node SortedInsert(Node head,int data) { Node ins = new Node(); ins.data = data; Node itr = head; //case: empty list if(head == null) { return ins; //case: at begining of list } else if(head.data > data) { ins.next = head; head.prev = ins; return ins; } else { while(itr.data < data) { if(itr.next == null) { // case: at end of list itr.next = ins; ins.prev = itr; return head; } else { itr = itr.next; } } // case: somewhere in middle itr.prev.next = ins; ins.prev = itr.prev; itr.prev = ins; ins.next = itr; return head; } }
RodneyShag I almost always use just 1 pointer when working with linked lists as it makes for cleaner code. That's how I originally coded this problem. Using 2 pointers was my 2nd approach and it turned out nice. Nice job.
RJB3_MechLearn Translated into Python. In Pytohn head = Node(0, None, None)
def SortedInsert(head, data): new_node = Node() new_node.data = data # in the unlikely event new node data < 0? if new_node.data < head.data: new_node.next = head head.prev = new_node return new_node else: this_node = head that_node = head.next while((that_node != None) and (new_node.data > that_node.data)): this_node = that_node that_node = that_node.next if that_node == None: this_node.next = new_node new_node.prev = this_node else: this_node.next = new_node that_node.prev = new_node new_node.prev = this_node new_node.next = that_node this_node = head while this_node!=None: this_node = this_node.next return head
anish20 Nicely done, used some what same logic in C++ , but didn't work. Then used your as a reference and implemented in C++. Worked nicely. Thanks.
Implementation in C++ similar to yours.
/* Insert Node in a doubly sorted linked list After each insertion, the list should be sorted Node is defined as struct Node { int data; Node *next; Node *prev; } */ Node* SortedInsert(Node *head,int data) { // Complete this function // Do not write the main method. struct Node *new_node = new Node(); struct Node* temp = head; new_node->data = data; //case when List is empty if(head==NULL) { head = new_node; return head; } //insertion at beginning of List else if(data < temp->data) { new_node->next = temp; temp->prev = new_node; head = new_node; return head; } //walking with 2 pointers else{ struct Node* temp1 = NULL; //traversing only if new_node has larger data while(temp!= NULL && temp->data < data) { temp1 = temp;//temp1 is node previous to temp temp=temp->next; } //insertion at end of LL if(temp==NULL) { temp1->next = new_node; new_node->prev = temp1; new_node->next = NULL; } //insertion in between //temp1 is node prev to temp //temp is ahead of temp1 //new_node has to be inserted between temp and temp1 else{ temp1->next = new_node; temp->prev = new_node; new_node->next = temp; new_node->prev = temp1; } return head; } }
yashkrsingh [deleted]sairamya_m96 Solution.java:71: error: constructor DoublyLinkedListNode in class DoublyLinkedListNode cannot be applied to given types; DoublyLinkedListNode newNode = new DoublyLinkedListNode(); ^ required: int found: no arguments reason: actual and formal argument lists differ in length 1 error
Im getting this with this code..can u help me
eliodeb Long commented C++ implementation.
Node* SortedInsert(Node *head,int data) { Node* temp = head; //Initializing the new Node Node* newNode = new Node(); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; // If thr List is empty point the head to the new node if(temp == NULL) { temp = newNode; head = temp; return head; } //Check if the data in the new node is bigger // or smaller than each node in the list. if it's // bigger, move to the next node in the list. // If it's the last node stop. while((newNode->data > temp->data) && temp->next != NULL) { temp = temp->next; } //If it was the last node and the data is still //bigger this new node will be added to the tail if(temp->next == NULL && newNode->data > temp->data ) { newNode->prev = temp; temp->next = newNode; return head; } //If this was smaller than the node pointed by temp //we add new node before it newNode->prev = temp->prev; temp->prev = newNode; newNode->next = temp; //If there are elements before we need to link its //next to our new node if(newNode->prev != NULL) { newNode->prev->next = newNode; } //If there are no elements before it, our node //is the first one so we point the head/temp to it if(newNode->prev == NULL) { temp = newNode; return temp; } return head; }
himanshuladia The following code treats corner cases explicitly. Seems much cleaner to me.
Node* SortedInsert(Node *head,int data) { Node* ptr = head; Node* temp = new Node(); temp->data = data; temp->next = NULL; temp->prev = NULL; // If the list is empty if(head == NULL){ head = temp; return head; } // If node is to be inserted at 1st place if(data < head->data){ temp->next = head; head->prev = temp; head = temp; return head; } while(ptr!=NULL){ // If node is inserted in between if(data<ptr->data){ temp->next = ptr; temp->prev = ptr->prev; ptr->prev->next = temp; ptr->prev = temp; return head; } //If node is inserted at the end if(ptr->next==NULL){ temp->prev = ptr; temp->next = NULL; ptr->next = temp; return head; } ptr = ptr->next; } //To avoid Werror return head; }
mindofmateo Whoever submitted this did not follow the conventions to which the other Linked List challenges adhere to and as such made this a real booger to solve. Jesus.
shubhampachori6 Python Recursion:
def SortedInsert(head, data): node = Node(data,None,None) if (head == None): return node elif (data < head.data): node.next = head head.prev = node return node else: node = SortedInsert(head.next, data) head.next = node node.prev = head return head
zhalzel Very nice, thanks!
in C++
Node* makeNode(int data){ Node* newNode = (Node*) malloc(sizeof(Node)); newNode->data = data; newNode->next = 0; newNode->prev = 0; return newNode; } Node* SortedInsert(Node *head,int data){ if (!head) { Node* newNode = makeNode(data); return newNode; } if (data < head->data){ Node* newNode = makeNode(data); newNode->next = head; head->prev = newNode; return newNode; } else{ head->next = SortedInsert(head->next, data); head->next->prev = head; return head; } }
neerajkumar8575 Node* SortedInsert(Node *head,int data) { // Complete this function // Do not write the main method. struct Node *temp = new Node; struct Node *store = head; temp->data = data; temp->next = NULL; temp->prev = NULL;
if(head == NULL) { return temp; } else { if(data > head->data ) { while((head->next != NULL ) && (data > head->next->data) ) { head = head->next; } if(head->next == NULL) { temp->next = head->next; temp->prev = head; head->next = temp; return store; } temp->next = head->next; temp->prev = head; head->next = temp; temp->next->prev = temp; return store ; } else { temp->next = head; head->prev = temp; return temp; } } return store;}
HHWWHH Python Iteration:
def SortedInsert(head, data): temp=Node(data) if head==None: head=temp else: cur=head if cur.data>=data: #insert temp to head temp.next=cur cur.prev=temp return temp else: #insert temp to non-head part of list while cur.next!=None: if cur.data<data and cur.next.data>=data: temp.next=cur.next cur.next.prev=temp cur.next=temp temp.prev=cur break else: cur=cur.next else: cur.next=temp temp.prev=cur return head
talsa static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) { if (head == null) return new DoublyLinkedListNode(data); if(head.data > data) { DoublyLinkedListNode node = new DoublyLinkedListNode(data); node.next = head; return node; } head.next = sortedInsert(head.next, data); return head; }
ghsatpute Why do I get
0 0 0 0
After running following code
Node ptr = head; while (ptr != null) { System.out.print(ptr.data + "\t"); ptr = ptr.next; }
Also, printing
head.datareturns0:(Can anybody explain this?
MakeItHappen I think head is never null. You should to test head.data == 0 instead.
gh0stc0d3r That's because head.data is 0.
ghsatpute Can you explain why head.data is 0 always?
gh0stc0d3r The test cases are designed this way I think. The linked list provided to us already has one element that is 0. See here.
mvj3_ The strategy is to find the two nodes before and after 'data', but the tricky thing here is that both could be missing, so we add a faked root here before the head.
def sortedInsert(head, data): root = DoublyLinkedListNode(0) root.next = head curr = root while curr.next and (data > curr.next.data): curr = curr.next next_node = curr.next curr.next = DoublyLinkedListNode(data) curr.next.prev = curr curr.next.next = next_node return root.next
Sort 401 Discussions, By:
Please Login in order to post a comment