Tuesday, October 9, 2012

Suffle Merge

Given two lists, merge their nodes together to make one list, taking nodes alternately between the two lists. So ShuffleMerge() with {1, 2, 3} and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1}.

/*
 * Merge the nodes of the two lists into a single list taking a
 * nodes alternately from each list, and return the new list.
 */
nodeptr ShuffleMerge(nodeptr a, nodeptr b)
{
    nodeptr current = NULL, tempnode = NULL;
    if (a == NULL && b == NULL) return NULL;
    else if (a == NULL) return b;
    else if (b == NULL) return a;
    else {
        current = a;
        tempnode = current->next;
        while(current->next != NULL && b->next != NULL)
        {
            current->next = b;
            b = b->next;
            current = current->next;
            current->next = tempnode;
            current = current->next;
            tempnode = current->next;
        }
        if(b)
            current->next = b;
        if(current)
            current->next = tempnode;
        return a;
    }
}

No comments:

Post a Comment