Aug 282012
 

Given two linked list with Node values sorted in ascending order.

Write function that accepts these two linked lists, merge them and return pointer to merged list.

In the process Original lists should be deleted (the pointer to head of original lists should be set to NULL)

 Solution:

This is as simple as merging two arrays, even simpler than that because here we just need to move pointers.

let h1 and h2 point to the head of two lists
h3 = NULL
While Both h1 and h2 are valid pointers
    IF (h1.data < h2.data)
        append h1 to h3 
        Move h1 forward
    ELSE
        append h2 to h3 
        Move h2 forward
IF(h1 has more Nodes)
    append all the nodes to h3
ELSE
    Append all nodes from h2 to h3
return h3.

Code:

/** 
 * Delete all the Nodes from the two lists, merge them 
 * and return pointer to the head of merged list.
 *
 * Because we are deleing the original lists, we need Node** and not Node* as parameter.
 */
Node* mergeLists(Node** originalH1, Node** originalH2)
{
    // Deleting the original lists...
    // don't need to delete actual nodes, because they will be moved to merged list.
    Node* h1 = *originalH1;
    Node* h2 = *originalH2;
    *originalH1 = *originalH2 = NULL;

// ACTUAL MERGING CODE STARTS FROM HERE

    // Head of merged list
    Node* h3 = NULL;

    // point to the end of merged list
    // Need this because we append node to the end of new list
    Node* tail = NULL;

    while(h1 != NULL && h2 !=NULL)
    {
        if(h1->data < h2->data)
        {
            if(h3 == NULL)
            {
                h3 = tail = h1;
            }
            else
            {
                tail->link = h1;
                tail = h1;
            }
            h1 = h1->link;
        }
        else
        {
            if(h3 == NULL)
            {
                h3 = tail = h2;
            }
            else
            {
                tail->link = h2;
                tail = h2;
            }
            h2 = h2->link;
        }
    }

    // Adding the remaining elements to result list
    if(h1 == NULL)
    {
        if(h3 == NULL)
            h3 = h2;
        else
            tail->link = h2;
    }
    else
    {
        if(h3 == NULL)
            h3 = h1;
        else
            tail->link = h1;
    }
    return h3;
}

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)