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.
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?
bhupankarg [deleted]abhimanyuaj001 [deleted]abhimanyuaj001 [deleted]abhimanyuaj001 solution in python
def sortedInsert(head, data): cur=head node=DoublyLinkedListNode(data) if cur.data>data or cur.data==data: node.next=cur cur.prev=node head=node return head while cur.next: if (cur.data<data and cur.next.data>data) or cur.data==data: node.next=cur.next cur.next.prev=node node.prev=cur cur.next=node return head cur=cur.next if cur.data<data or cur.data==data: node.prev=cur cur.next=node return head
Ghos3t It seems that the Problem Statement has changed over time, this solution passes all the test cases, but it only inserts the given data at the correction position in the given Doubly Linked List, it won't generate a sorted list as a outpout. The doubly linked list will only be sorted if the nodes given as input are already in a sorted order. For example if the following input is given-
1 // Number of Test Cases
4 // Number of elements in the Linked List
2
1
4
3
8 // The the data which need to be inserted in the doubly linked listThe the final output will be -
2 1 4 3 8
as you can see the new data is inserted in the correct order but the doubly linked list itself will remain unsorted. But since all the test cases give the nodes in a sorted order this issue doesn't seem to matter
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.
naisargioza24 DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) {
if(head==NULL) { DoublyLinkedListNode* temp=new DoublyLinkedListNode(data); head=temp; } else if(head->data>=data) { DoublyLinkedListNode* newnode= new DoublyLinkedListNode(data); newnode->prev=NULL; newnode->next=head; head->prev=newnode; head=newnode;}
else { DoublyLinkedListNode* newnode=new DoublyLinkedListNode(data); DoublyLinkedListNode* temp=head; while(temp->next->data<data && temp->next!=NULL) { temp=temp->next; } if(temp->next!=NULL) { DoublyLinkedListNode* t=temp; t=t->next; temp->next=newnode; t->prev=newnode; newnode->next=t; newnode->prev=temp; } else { temp->next=newnode; newnode->prev=temp; newnode->next=NULL; } } return head; } What is wrong in this code?It does not work when the element is to be inserted at the end of the listadityabhandari13 Same problem dude
sweths98 did you rectify? same problem!
adityabhandari13 Nope
aayushjha48 In while loop inside else , when temp is pointing to last node the while loop will terminate (as temp->next == NULL will be false) thus you have to write additional code for the last node below while loop.
isaminder8 if(head==NULL) { DoublyLinkedListNode* temp=new DoublyLinkedListNode(data); head=temp; } else if(head->data>=data) { DoublyLinkedListNode* newnode= new DoublyLinkedListNode(data); newnode->prev=NULL; newnode->next=head; head->prev=newnode; head=newnode; } else { DoublyLinkedListNode* newnode=new DoublyLinkedListNode(data); DoublyLinkedListNode* temp=head; while(temp==NULL || temp->next->data<data) { if(temp->next->data>data || temp->next->next==NULL) { temp=temp->next; break; } temp=temp->next; } if(temp->next!=NULL) { DoublyLinkedListNode* t=temp; t=t->next; temp->next=newnode; t->prev=newnode; newnode->next=t; newnode->prev=temp; } else { temp->next=newnode; newnode->prev=temp; newnode->next=NULL; } } return head;
paryush Add another condition to handle the End case:
if(temp->next == nullptr){ new_node->prev = temp; temp->next = new_node; break; }
dhingra_ankush05 Simpler code in java
static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) { DoublyLinkedListNode temp=head; DoublyLinkedListNode currentnode=new DoublyLinkedListNode(data); if(head.data>data) { currentnode.next=head; head=currentnode; } else { while(temp.next!=null && temp.data<data) { temp=temp.next; } if(temp.next==null && temp.data<data) { temp.next=currentnode; currentnode.prev=temp; return head; } else{ currentnode.prev=temp.prev; currentnode.next=temp; currentnode.prev.next=currentnode; temp.prev=currentnode; } } return head; }
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.
benriegel [deleted]kevinmandalia It may work, but think about stack space for large lists. Try come up with an iterative solution.
madhokdivyam else if (data <= head.data) { n.next = head; head.prev = n; return n; }
In this case when data<= head.data, why di you assume that the rest of the linked list will be sorted?
CSociety @calvin_cheng_cc I think we don't need to create a new node "rest". Inspite we can use head.next like this to move forward in linked list
head.next = SortedInsert(head.next, data);
janis_stolzenwa1 excellent recursive solution!
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?
subhashsagar98 use struct DoublyLinkedListNode* new_node = (struct DoublyLinkedListNode*)malloc(sizeof(struct DoublyLinkedListNode)); instead of struct DoublyLinkedListNode* new_node;
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.
pruthivardaan Your code wont work if the new node's data is less than the head node's data. For that you have to add an if-else loop to your code with your code in the else part with the if part as : (ps. i created a new node at the start of the method , so you can change your code accordingly or create seperate node for this case)
if (temp.data>= data){ newnode.next=temp; temp.prev=newnode; newnode.prev=null; return newnode; }
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
sailendri I too got this error.It is because,the value of data is not passed during the construction of newnode.Note that I have passed the value of newnode's data. This java code worked for me:) static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) { DoublyLinkedListNode n = new DoublyLinkedListNode(data); n.data = data; if(head == null) { return n; } else if (data <= head.data) { n.next=head; head.prev=n; return n; } else { DoublyLinkedListNode rest = sortedInsert(head.next,data); head.next=rest; rest.prev=head; return head; } }
baymaxlim2204 I had the same idea. Separating the cases for inserting in the middle, appending and prepending. But I'm trying to find a solution thats all-in-one.
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
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
sharmakaran1244 can you please explain me the else part or test case 7 ???
I wrote with diffferent approach and it is bigger code, this is my else part----->
else:
current=last=head while(current.data<data): if(current.next==None): current.next=DoublyLinkedListNode(data) current.next.next=None return head last=current current=current.next last.next=DoublyLinkedListNode(data) last.next.next=current return head
Sort 637 Discussions, By:
Please Login in order to post a comment