Merge two sorted lists (in-place)

Given two sorted lists, merge them so as to produce a combined sorted list (without using extra space).

Examples:

Input : head1: 5->7->9
        head2: 4->6->8 
Output : 4->5->6->7->8->9

Input : head1: 1->3->5->7
        head2: 2->4
Output : 1->2->3->4->5->7

Node *merge(Node *h1, Node *h2)

{

    if (!h1)

        return h2;

    if (!h2)

        return h1;

 

    // start with the linked list

    // whose head data is the least

    if (h1->data < h2->data)

    {

        h1->next = merge(h1->next, h2);

        return h1;

    }

    else

    {

        h2->next = merge(h1, h2->next);

        return h2;

    }

}