Function to smooth the list into one list

Question

Given the structure of a linked list, where each node is a linked list and contains two pointers of its type:

(i) a pointer to the next node in the main list.
(ii) a pointer to a linked list where this node is the head.

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

Eg.

If this linked list

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

then convert it to

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

My decision

 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 optimization are welcome

Answer 1

First, it is important that it works. Due to while(temp->fwd!=NULL) your solution does not 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, does not apply to node->down->fwd . You can solve this problem with a recursive function that remains as an exercise.

Answer 2

If you consider the link "down" as the left child pointer, and the "direct" link as the correct child pointer, then you are looking for a crawl in the order of a simple binary tree. That is, you are visiting node; then you visit the left (down) children, then you visit the right (forward) children. It is very easy to write this as a recursive function.

Your solution will not go through any of the trees if the first node had only a down pointer and did not point forward. Also, he would not look down from the last pointer if he had down pointers (because he does not have a forward pointer).

I think (but I'm not sure that I have not tested it) that your solution runs into problems on thicker trees than in the example. If node 2 had pointers to pointers, I think there will be problems finding this subtree.

Use recursion; it is trivial and reliable. Although you can eliminate simple tail recursion, it requires simpler tail recursion.

Answer 3

 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; } 

Answer 4

The solution looks good to me. A small change may be that from the solution diagrams, I expect the answer to be a “horizontal” list (using fwd pointers), and not the vertical (using down pointers) that your solution creates

Answer 5

  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; } }