Merge method C++

I want to write a method that merges two lists together in an alternating manner. So if I have list1=(0,1,2,3,4) and list2=(5,6,7,8), then the final list should b开发者_JAVA技巧e (0,5,1,6,2,7,3,8,4). Do you any ideas or hints, because I've tried so many things, but all fail to make sense.

That's pretty trivial if you don't need to keep the original lists intact.

algorithm would look like something like that:

1. start from the head of list 1, go to item 1 (1.1)

2. pick the corresponding item (2.1) from the list 2, change its head to the list 1 head, its prev to list 1 current item (1.1), change the current item next pointer to 2.1, and change 1' next pointer to point to 1.2. Make sure that 1.2 prev points to 2.1 now.

3. Move to 1.2 and 2.2 on each list, and repeat, until the end.

// I've been doing Java for a few years now, so my pointers are a bit rusty...
// Forgive pointer errors and focus on concept
/** 
 * @Param list1 the pointer to the head of the first list
 * @Param list2 the pointer to the head of the second list
 * Assumption - list 1 will be able to swallow list 2 without overflowing
 *              handling that is left to OP
 */
void mergeInto(Node *list1, Node *list2) {
    Node curr1 = list1;
    Node curr2 = list2;

    while(curr2 != null) {
        // store after nodes
        Node after1 = curr1.next;
        Node after2 = curr2.next;

        // link curr2 into list1
        curr1.next = curr2;
        curr2.prev = curr1;

        after1.prev = curr2;
        curr2.next = after1;

        // move on to the next in list2
        curr2 = after2;
    }


}