// Examples of circular lists and special cases where constant time
// is obtained.
// See CSE 2320 Notes 9
#include <stdlib.h>
#include <stdio.h>

typedef struct listNode listNodeType;

struct listNode {
  int content;
  listNodeType *next;
};

void printCircularList(listNodeType *x)
{
listNodeType *work;

printf("Printing circular list\n");
// Can't use for-loop here
work=x;
while (1)
{
  printf("%d\n",work->content);
  work=work->next;
  if (work==x)
    return;
}
}

void printList(listNodeType *x)
{
listNodeType *work;

printf("Printing ordinary list\n");
for (work=x;work;work=work->next)
  printf("%d\n",work->content);
}

int main()
{
int i;
listNodeType *work;
listNodeType temp;
listNodeType garbage[10],*G;
listNodeType zeeList[5],*z;
listNodeType xList[3],*x;
listNodeType yList[3],*y;

// Initialize garbage list
G=garbage;
for (i=0;i<9;i++)
  garbage[i].next=(&garbage[i+1]);
garbage[9].next=NULL;
for (i=0;i<10;i++)
  garbage[i].content=i;

// Initialize circular list
z=zeeList;
for (i=0;i<4;i++)
  zeeList[i].next=(&zeeList[i+1]);
zeeList[4].next=zeeList;
for (i=0;i<5;i++)
  zeeList[i].content=(-i-1);

printList(G);
printCircularList(z);
// Include zeeList on garbage list
work=z->next;
z->next=G;
G=work;
printList(G);

x=xList;
xList[0].content=1;
xList[1].content=2;
xList[2].content=3;
xList[0].next=(&xList[1]);
xList[1].next=(&xList[2]);
xList[2].next=x;
y=yList;
yList[0].content=4;
yList[1].content=5;
yList[2].content=6;
yList[0].next=(&yList[1]);
yList[1].next=(&yList[2]);
yList[2].next=y;
printCircularList(x);
printCircularList(y);

// Concatenate x and y by swapping first nodes.
temp=(*x);
(*x)=(*y);
(*y)=temp;
x=y;
printCircularList(x);
}