Merge two sorted linked lists such that merged list is in reverse order - GeeksforGeeks

Merge two sorted linked lists such that merged list is in reverse order - GeeksforGeeks
Given two linked lists sorted in increasing order. Merge them such a way that the result list is in decreasing order (reverse order).

// Given two non-empty linked lists 'a' and 'b'

Node* SortedMerge(Node *a, Node *b)

{

    // If both lists are empty

    if (a==NULL && b==NULL) return NULL;

 

    // Initialize head of resultant list

    Node *res = NULL;

 

    // Traverse both lists while both of then

    // have nodes.

    while (a != NULL && b != NULL)

    {

        // If a's current value is smaller or equal to

        // b's current value.

        if (a->key <= b->key)

        {

            // If this is the first Node to be added to

            // result list 'res'

            if (res == NULL)

            {

                // Make 'a' as head of result list

                res = a;

 

                 // Move ahead in first list

                a = a->next;

                res->next = NULL;

            }

            else // If there are already Nodes in 'res'

            {

                // Store next of current Node in first list

                Node *temp = a->next;

 

                // Add 'a' at the front of resultant list

                a->next = res;

                res = a;

 

                // Move ahead in first list

                a = temp;

            }

        }

 

        // If a's value is greater. Below steps are similar

        // to above (Only 'a' is replaced with 'b')

        else

        {

            if (res == NULL)

            {

                res = b;

                b = b->next;

                res->next = NULL;

            }

            else

            {

                Node *temp = b->next;

                b->next = res;

                res = b;

                b = temp;

            }

        }

    }

 

    // If second list reached end, but first list has

    // nodes. Add remaining nodes of first list at the

    // front of result list

    while (a != NULL)

    {

        Node *temp = a->next;

        a->next = res;

        res = a;

        a = temp;

    }

 

    // If first list reached end, but second list has

    // node. Add remaining nodes of first list at the

    // front of result list

    while (b != NULL)

    {

        Node *temp = b->next;

        b->next = res;

        res = b;

        b = temp;

    }

 

    return res;

}

Read full article from Merge two sorted linked lists such that merged list is in reverse order - GeeksforGeeks