Tuesday, August 17, 2010

Microsoft Question: Merge Two linked list without creating any new node

My Solution is in C++ and is as follows --


void list::merge(list& l1)
{
    if(this == &l1)       // same list
        return;
    node *t1 = head;
    node *t2 = l1.head;
    node *temp1 = NULL, *temp2 = NULL;
    if(t1->data > t2->data)
    {
        temp2 = t2->next;
        t2->next = t1;
        head = t2;
        t2 = temp2;
    }
    else
        t1 = t1->next;
    node* prev = head; // prev is must as we need to have previous pointer to insert node at a given position
    while(t1&&t2)
    {
        if(t1->data <= t2->data)
            t1=t1->next;
        else
        {
            temp1 = prev->next;
            temp2 = t2->next;
            prev->next = t2;
            t2->next = temp1;
            t2 = temp2;
        }
        prev = prev->next;
    }

    if(!t1)
        prev->next=t2;
}

1 comment:

  1. If any body has better solution or is able to get flaws, Please tell me.

    ReplyDelete