Thursday, 23 April 2015

Merge two sorted linked list in a sorted order

//merge two sorted linked list in sorted order

void MoveNode(struct node **dest , struct node **src)
{
    struct node* newNode = *src;
   
    assert(newNode != NULL) ;
   
    //advance src
    *src = newNode->next;
   
    //link new node with destination old reference
    newNode->next = *dest;
   
    //point dest to new node
    *dest = newNode;
   

}


struct  node*  merge(struct node** a , struct node** b )
{
    struct node dummy;
   
   
    //pointer to tail for easy appendinng at end of list in MoveNode()
    struct node* tail = &dummy;
   
    dummy->next = NULL;
   
    while(1)
    {
        if( a == NULL)
        {
            tail->next = b ;
            break;
        }
        else if( b == NULL)
        {
            tail->next = a ;
            break;
        }
        else if (a->data <= b->data)
        {
            MoveNode(&(tail->next) , &a);
        }
        else
        {
            MoveNode(&(tail->next) , &a);
        }
        tail = tail->next;
    }
   
    return ( dummy -> next);
}

No comments:

Post a Comment