function to flatten list in to single list

Given a linked list structure where every node represents a linked list and contains two pointers of its type:

(i) pointer to next node in the main list.

(ii) pointer to a linked list where this node is head.

Write a C function to flatten the list into a single linked list.

Eg.

If the given linked list is

  1 -- 5 -- 7 -- 10 
  |    |    | 
  2    6    8 
  |    | 
  3    9 
  | 
  开发者_C百科4 

then convert it to

1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10 

My solution

struct node {
    int data; 
    struct node *fwd; //pointer to next node in the main list. 
    struct node *down; //pointer to a linked list where this node is head. 
}*head,*temp,*temp2; 

temp=head; 
while(temp->fwd!=NULL) {
    temp2=temp->fwd; 
    while(temp->down!=NULL) {
        temp=temp->down;
    } 
    temp->down=temp2;
    temp->fwd=NULL;
    temp=temp2;
 }  

plz notify me if anything...other solutions and optimizations are welcome

First it's important to get it working. Because of while(temp->fwd!=NULL), your solution doesn't work for these scenarios:

A) 1 -- 2     B) 1 -- 3
        |        |    |
        3        2    4

Try this instead:

#include <stdio.h>

struct node {
    int data;
    struct node *fwd; //pointer to next node in the main list.
    struct node *down; //pointer to a linked list where this node is head.
};

struct node *solve(struct node *head) {
    struct node *temp = head, *fwd;
    while (temp != NULL) {
        fwd = temp->fwd;
        while (temp->down != NULL) {
            temp = temp->down;
        }
        temp->down = fwd;
        temp->fwd = NULL;
        temp = fwd;
    }
    return head;
}

int main(int argc, char **argv) {
    struct node
        n12 = { 12, NULL, NULL },
        n11 = { 11, NULL, &n12 },
        n10 = { 10, NULL, &n11 },
        n8 = { 8, NULL, NULL },
        n7 = { 7, &n10, &n8 },
        n9 = { 9, NULL, NULL },
        n6 = { 6, NULL, &n9 },
        n5 = { 5, &n7, &n6 },
        n4 = { 4, NULL, NULL },
        n3 = { 3, NULL, &n4 },
        n2 = { 2, NULL, &n3 },
        n1 = { 1, &n5, &n2 },
        *result = solve(&n1);

    while (result != NULL) {
        printf("%d%s", result->data, result->down ? " - " : "");
        result = result->down;
    }
    puts("");

    return 0;
}

Note: This of course doesn't deal with node->down->fwd. You may want to solve that using a recursive function, which is left as exercise.

If you treat the 'down' link as being the left child pointer, and the 'forward' link as the right child pointer, then you are seeking an in-order traversal of a simple binary tree. That is, you visit the node; then you visit the left (down) children, then you visit the right (forward) children. It is very easy to write that as a recursive function.

Your solution would not traverse any of the tree if the first node had only a down pointer and no forward pointer. Nor would it search downwards from the last pointer if that had down pointers (because it has no forward pointer).

I think (but I'm not certain - I haven't tested it) that your solution runs into trouble on bushier trees than the one in the example. If node 2 had forward pointers, I think there would be problems getting that subtree searched.

Use recursion; it is trivial and reliable. While you can eliminate simple tail recursion, this requires more than simple tail recursion.

struct node* flatten_dfwalk(struct node * root)
{   

    struct node *lnode, *rnode, *temp;

    if (NULL == root)
    {
        return NULL;
    }


    lnode = flatten_dfwalk(root->down);
    rnode = flatten_dfwalk(root->next);

    if (NULL == lnode)
    {
        return root;
    }

    temp = lnode;
    while(lnode->next != NULL)
    {
        lnode = lnode->next;
    }

    lnode->next = root->next;
    root->next = temp;

    return root;
}

Solution looks OK to me. A minor change might be that from the diagrams of the solution, I would expect the answer should be a "horizontal" list (using the fwd pointers) rather then the vertical one (using the down pointers) that your solution produces

    struct node * last;
    void dfs(struct node * root)
    {
        if(root)
        {
            dfs(root->down);
            if(last!=NULL)
            {
                last->next=root->next;
                last=NULL;
            }
            dfs(root->next);
            if(root->down)
            root->next=root->down;

            if(root->next==NULL&&root->down==NULL)
                last=root;
        }
    }