Insert Node in a Sorted Doubly linked list

algorithm, c++, data-structures, doubly-linked-list

Solution

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

Problem

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

Original source