Insert Node in a Sorted Doubly linked list

Vansh Khurana picture Vansh Khurana · Dec 1, 2013 · Viewed 18.3k times · Source

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

Abhishek Bansal picture Abhishek Bansal · Dec 1, 2013

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