I am not able to figure out, why is my code to insert into a sorted doubly linked list failing on some test cases.Please let me know. I dont know of the test cases, they are system generated.
Node* SortedInsert(Node *head,int data)
{
// Complete this function
// Do not write the main method.
Node * temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->next = NULL;
temp->prev = NULL;
if (head == NULL)
{
head = temp;
return head;
}
if (temp->data <= head->data)
{
temp->next = head;
head->prev = temp;
head = temp;
return head;
}
Node *curr = head;
while (curr->next!=NULL)
{
if (temp->data <= curr->data)
{
curr->prev->next = temp;
temp->prev = curr->prev;
temp->next = curr;
curr->prev = temp;
return head;
}
curr = curr->next;
}
curr->next = temp;
temp->prev = curr;
return head;
}
Thanks
Once you reach the last node, you should again compare its data with the new node and insert accordingly.
curr->next = temp;
temp->prev = curr;
return head;
}
If execution reaches this part, then at present curr is pointing to the last node. Now you should again compare its data like the following:
if (temp->data <= curr->data)
{ // insert before last node
curr->prev->next = temp;
temp->prev = curr->prev;
temp->next = curr;
curr->prev = temp;
return head;
}
// else insert at the end.
curr->next = temp;
temp->prev = curr;
return head;
}