function to flatten the list into a single linked 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
|
4
then convert it to
1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10
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
|
4
then convert it to
1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10
#include
ReplyDeletestruct 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;
}