Flatten a linked list in c

October 19, 2022

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

}

>Solution :

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