// Example of destructive merge of ordered lists with header and sentinel
// See CSE 2320 Notes 9
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct listNode listNodeType;
typedef listNodeType* listNodeTypePtr;

struct listNode {
  int content;
  listNodeTypePtr next;
};

listNodeTypePtr init(int key,listNodeTypePtr ptr) {
  // Constructs a new list node
  listNodeType *work;

  work=(listNodeTypePtr) malloc(sizeof(listNodeType));
  if (!work)
    assert("malloc");
  work->content=key;
  work->next=ptr;
  return work;
  }

listNodeTypePtr merge(listNodeTypePtr x, listNodeTypePtr y) {
  // Destructive union, discarding duplicate keys
  // Assumes shared sentinel
  listNodeTypePtr z=x,
                  zLast=x, // reuse header for result
                  yWork;

  x=x->next;
  yWork=y;
  y=y->next;
  free(yWork); // discard header  
  while (x!=y) // could test with (x->content<9999 && y->content<9999)
    if (x->content<y->content) {
      zLast=zLast->next=x;
      x=x->next;
      }
    else if (x->content>y->content) {
      zLast=zLast->next=y;
      y=y->next;
      }
    else { // contents are the same
      zLast=zLast->next=x;
      x=x->next;
      yWork=y;
      y=y->next;
      free(yWork); // discard
      }

  return z;
  }

void printList(listNodeTypePtr x) {
  printf("List contents:\n");
  x=x->next;
  while (x->content!=9999) {
    printf("%d\n",x->content);
    x=x->next;
    }
  }

int main() {
  listNodeTypePtr sentinel=init(9999,NULL); // shared sentinel!!!
  listNodeTypePtr x,y,z;

  // Two ordered lists with headers
  x=init(-9999,init(1,init(5,init(7,init(13,sentinel)))));
  y=init(-9999,init(2,init(3,init(5,init(11,init(17,sentinel))))));
  printList(x);
  printList(y);
  z=merge(x,y);
  printList(z);
  }