I have been trying to make this problem, but i have not been able to complete it. It's a linked list (only next or down, multilevel linked list), each node can have children, like this graph:
1c -> 3 -> 5c -> 7
| |
2 4
|
9
To flatten the list, all the children have to be moved to the right of their parent node in order. This should be the result:
"List : 1 2 3 5 4 9 7"
I have tried with this code, but i don't understand how i can make the effects on the create_list function and then print it with the changes.
This is my code so far:
#include <stdio.h>
#include <stdlib.h>
//Flatten linked list problem
typedef struct node
{
int data;
struct node *next;
struct node *down;
}node;
node node1, node2, node3, node4, node5, node6, node7;
node *head;
void create_list()
{
node1.data = 1; node1.down = &node5; node1.next = &node2;
node2.data = 3; node2.down = NULL; node2.next = &node3;
node3.data = 5; node3.down = &node7; node3.next = &node4;
node4.data = 7; node4.down = NULL; node4.next = NULL;
node5.data = 2; node5.down = NULL; node5.next = NULL;
node6.data = 5; node6.down = &node7; node6.next = NULL;
node7.data = 0; node7.down = NULL; node7.next = NULL;
head = &node1;
}
void print(node *header)
{
node * temp = header;
printf("List : ");
while(temp != NULL)
{
printf("%d%s ", temp->data, (temp->down) ? "c":""); //c = has a child
temp = temp->next;
}
printf("\n");
}
void expand(node *h)
{
/*
node *ptr = h, *temp_next, *n;
while (ptr)
{
if(ptr->down)
{
temp_next = ptr->next;
ptr->next = ptr->down;
ptr->next = ptr;
ptr->down = NULL;
n = ptr->next;
while (n->next) n = n->next;
n->next = temp_next;
if(n->next) n->next= n;
}
ptr = ptr->next;
}
*/
}
int main()
{
create_list();
printf("Before: \n");
print(head);
//Flatten the list
expand(head);
printf("After: \n");
print(head);
}
CodePudding user response:
This loop goes node by node moving all nodes connected via down
pointers to the next
pointer while preserving the order of the list.
for(node *pt = head; pt != NULL; pt = pt->next)
if(pt->down){
pt->down->next = pt->next;
pt->next = pt->down;
pt->down = NULL;
}
If the logic of this solution is not clear, it may be worthwhile to read up on pointers as well as linked lists, binary trees, and other related data structures