list_unique_merge

list_unique_merge

#include <stdio.h>
#include <stdlib.h>
struct node_t {
   struct node_t* next;
   int value;
};

typedef struct node_t node_t;
typedef struct {
   node_t* head;
} list_t;

//< assume that no duplicated items in list_t and list_t itself is sorted
void list_unique_merge(list_t* a, list_t* b)
{
   if (a==0) return;
   if (b==0) return;

   node_t* A = a->head;
   node_t* B = b->head;

   if (B==0) return;
   if (A==0) {
      a->head = B;
      b->head = 0;
      return;
   }

   node_t* BB = B;
   node_t* AA = 0; // Parent of A
   while(B!=0) {
      BB = B;
      B = B->next;
      if (A->value > BB->value) {
	 printf("1. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 node_t* BBB = 0;
	 if(AA){
	    AA->next = BB;
	 } else {
	    BBB = BB; 
	 }
	 while (BB->next && BB->next->value < A->value) {
	    BB = BB->next;
	 }
	 printf("2. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 B = BB->next;
	 BB->next = A;
	 if (BBB) {
	    a->head = BBB;
	 }
	 continue;
      }
      if (A->value == BB->value) {
	 printf("3. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 free(BB);
	 continue;
      }
      if (A->next==0 /*&& A->value<BB->value*/) { // A$ < B*
	 printf("4. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 A->next = BB;
	 b->head = 0;
	 return;
      } 
      while(A->next && A->next->value < BB->value) {
	 AA = A;
	 A = A->next;
	 printf("X. A->value : %d, BB->value : %d\n", A->value, BB->value);
      }
      if (A->value == BB->value) {
	 printf("5. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 free(BB);
	 continue;
      }
      if (A->next==0 /*&& A->value<BB->value*/) { // A$ < B*
	 printf("6. A->value : %d, BB->value : %d\n", A->value, BB->value);
	 A->next = BB;
	 b->head = 0;
	 return;
      }
      printf("7. A->value : %d, BB->value : %d\n", A->value, BB->value);
      if (BB->value==A->next->value) {
	 free(BB);
	 continue;
      }
      BB->next=A->next;
      A->next=BB;
   }
}

int main ()
{
   list_t La;
   La.head = (node_t*) malloc(sizeof(node_t));
   if (La.head==0) return -1;
   La.head->value = -1;
   node_t* na = La.head;

   for (int j=1; j<32; ++j) {
      na->next = (node_t*) malloc(sizeof(node_t));       
      na->next->value = j*2;
      na = na->next;
   }

   list_t Lb;
   Lb.head = (node_t*) malloc(sizeof(node_t));
   if (Lb.head==0) return -1;
   Lb.head->value = -10000;
   node_t* nb = Lb.head;
   for (int j=-3; j < 32; ++j) {
      nb->next = (node_t*) malloc(sizeof(node_t));       
      nb->next->value = j*7;
      nb = nb->next;
   }
   na = La.head;
   while (na) {
      printf("%d ",na->value);
      na = na->next;
   }
   printf("\n");
   list_unique_merge(&La,&Lb);
   na = La.head;
   int k=0;
   while (na) {
      k++;
      printf("%d ",na->value);
      na = na->next;
   }
   printf("\n%d\n",k);
   list_unique_merge(&Lb,&La);
   na = Lb.head;
   k=0;
   while (na) {
      k++;
      printf("%d ",na->value);
      nb = na;
      na = na->next;
      free(nb);
   }
   printf("\n%d\n",k);
   return 0;
}