#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ELEMENT 1
#define SUBLIST 2
#define SUBLIST_PROB 0.25
#define TERM_PROB 0.25
#define LIST_SIZE 50

typedef struct _node {
   int type;
   int element;
   struct _node *sublist;
   struct _node *next;
} node;
typedef node *list;

list createList ( int *n, int level )
{
   list L = NULL;
   node *p, *q = NULL;
   double x;

   while (*n < LIST_SIZE) {
      if (level > 0) {
         x = (double)rand() / (double)RAND_MAX;
         if (x <= TERM_PROB) break;
      }
      p = (node *)malloc(sizeof(node));
      x = (double)rand() / (double)RAND_MAX;
      if (x <= SUBLIST_PROB) {
         p -> type = SUBLIST;
         p -> element = 0;
         p -> sublist = createList(n,level+1);
      } else {
         ++(*n);
         p -> type = ELEMENT;
         p -> element = 1 + rand() % 9;
         p -> sublist = NULL;
      }
      p -> next = NULL;
      if (q == NULL) L = q = p;
      else {
         q -> next = p;
         q = p;
      }
   }
   return L;
}

void printList ( list L )
{
   node *p;

   printf("(");
   p = L;
   if (p) {
      while (1) {
         if (p -> type == ELEMENT) printf("%d", p -> element);
         else if (p -> type == SUBLIST) printList(p -> sublist);
         else printf("?");
         p = p -> next;
         if (p == NULL) break;
         printf(",");
      }
   }
   printf(")");
}

/**** Flatten: Method 1 ****/

list flatten1 ( list L )
{
   list F = NULL;
   node *p, *q, *r = NULL;

   p = L;
   while (p) {
      if (p -> type == ELEMENT) {
         q = (node *)malloc(sizeof(node));
         q -> type = ELEMENT;
         q -> element = p -> element;
         q -> sublist = NULL;
         q -> next = NULL;
         if (F == NULL) F = r = q;
         else {
            r -> next = q;
            r = q;
         }
      } else if (p -> type == SUBLIST) {
         q = flatten1(p -> sublist);
         if (F == NULL) F = r = q; else r -> next = q;
         if (r) while (r -> next) r = r -> next;
      } else {
         fprintf(stderr, "+++ Error in flatten1(): unrecognized node...\n");
      }
      p = p -> next;
   }

   return F;
}

/**** Flatten: Method 2 ****/

/* The helper recursively populates the array A[] with the elements in L */
void flatten2helper ( list L, int *A, int *n )
{
   node *p;

   p = L;
   while (p != NULL) {
      if (p -> type == ELEMENT) {
         A[*n] = p -> element;
         ++(*n);
      } else if (p -> type == SUBLIST) {
         flatten2helper(p -> sublist, A, n);
      } else {
         fprintf(stderr, "+++ Error in flatten2(): unrecognized node...\n");
      }
      p = p -> next;
   }
}

list flatten2 ( list L )
{
   int *A, n;
   list F = NULL, p;

   /* First store the flattened list in an array A[] */
   A = (int *)malloc(LIST_SIZE * sizeof(int));
   n = 0;
   flatten2helper(L,A,&n);

   /* Prepare the flattened linked list F from the array A[]. Add A[n-1],
      A[n-2], ..., A[0] in that sequence at the beginning of F. */
   F = NULL;
   while (n) {
      p = (node *)malloc(sizeof(node));
      p -> type = ELEMENT;
      p -> element = A[n-1];
      p -> sublist = NULL;
      p -> next = F;
      F = p;
      --n;
   }

   free(A);

   return F;
}

int main ()
{
   list L, F, G;
   int n = 0;

   srand((unsigned int)time(NULL));

   L = createList(&n,0);
   printf("Original list:  "); printList(L); printf("\n");

   F = flatten1(L);
   printf("Flattened list: "); printList(F); printf("\n");

   G = flatten2(L);
   printf("Flattened list: "); printList(G); printf("\n");

   exit(0);
}