Vansh Khurana Vansh Khurana - 1 month ago 8
C++ Question

Insert Node in a Sorted Doubly linked list

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

Answer

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;
}
Comments