#define  nullE  ' '
#define  errV   ' '            
typedef char ElemType;

typedef struct NLNode {
    ElemType data;
    NLNode *next;
} *NLink, *Position;

typedef struct {
    NLink head, tail;
    int len;
} *NLinkList;

int equal(ElemType a, ElemType b);

int equal(ElemType a, ElemType b) {
    if(a == b) return TRUE;
    else return FALSE;
}

int Compare(ElemType a, ElemType b) {
    if(a < b) return -1;
    if(a > b) return 1;
    return 0;
}

int random2(int x, int y) {
    if(x >= y) return x;
    else return random(y - x) + x;
}

void get_purstr(char* str, int x) {
    int len, idx, kk;
    len = random(x);
    idx = random(10);
    kk = 0;
    while(kk < len && idx < 26) {
        str[kk] = 'A' + idx;
        idx = idx + random2(1, 4);
        kk++;
    }
    str[kk] = '\0';    
}

NLink MakeNode(ElemType e) {
    NLink p;
    if(!(p = (NLink)malloc(sizeof(NLNode)))) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    return p;
}

NLink FreeList(NLinkList L) {
    if(!L || !L->head) return NULL;
    NLink q, p = L->head;
    while(p) {
        q = p;
        p = p->next;
        free(q);
    }
    free(L);
    return NULL;
}
 
NLink InitList() {
    NLinkList L;
    if(!(L = (NLinkList)malloc(sizeof(*L)))) exit(OVERFLOW);
    if(!(L->head = L->tail = (NLink)calloc(1, sizeof(*L->head)))) exit(OVERFLOW);
    L->len = 0;
    return L;
}

Status ClearNList(NLinkList L) {
    if(!L || !L->head) return ERROR;
    NLink q, p = L->head->next;
    L->tail = L->head;
    L->head->next = NULL; 
    L->len = 0;
    while(p) {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

Status ListEmpty(NLinkList L) {
    if(L->head == L->tail || !L->head || !L->tail) return 1;
    else return 0;
}

int ListLength(NLinkList L) {
   if (L) return L->len; 
   else return 0;
}

NLink GetHead(NLinkList L) {
   if (!L) return NULL;
   return L->head;
}

Position LocatePos(NLinkList L, int i) {
    if(!L||i<0) return NULL;
    NLink p = L->head; int j = 0;
    while(p && j < i) {
        p = p->next; ++j;
    }
    if(!p) return NULL;
    return p;
}


NLink PrevPos(NLinkList L, NLink p){
    NLink q;
    if(!L || !p) return NULL;
    for(q = L->head; q&&q->next!=p; q = q->next);
    return q;
}

NLink NextPos(NLinkList L, NLink p) {  
   if (!L || !p) return NULL;
   return p->next;
}

Status SetCurElem(NLink p, ElemType e) {
   if (p) { p->data = e;   return OK; }
   else return ERROR;
}

ElemType GetCurElem(NLink p) {
   if (p) return p->data;
   else return nullE;
}
Status AppendOne(NLinkList L, NLink s) { 
   if (!L || !s) return ERROR;
   L->tail->next = s;
   L->tail = s;   L->len++;   return OK;
}       
Status Append(NLinkList L, NLink s) { 
   if (!L || !s) return ERROR;
   L->tail->next = s;
   while (s->next) s = s->next;    
   L->tail = s;   L->len++;   return OK;
}

Status InsAfter(NLinkList L, NLink *p, NLink s) {  
   if (!L || !*p || !s) return ERROR;
   NLink q;  q = *p;
   s->next = q->next;   q->next= s;  
   if (L->tail == q) L->tail = s;    
   L->len++;   *p = s;                
   return OK;
}

NLink DelAfter(NLinkList L, NLink p) {  
   if (!L || !p) return NULL;
   NLink q = p->next;
   p->next = q->next;
   if (L->tail == q) L->tail = p;    
   L->len--;
   return q;
}


NLinkList CreateNLList(char* ss) { 
   NLinkList L;   int i;   NLink p;
   if (!(L = (NLinkList)malloc(sizeof(*L)))) exit(OVERFLOW);
   if (!(L->head = (NLink)calloc(1, sizeof(NLNode)))) exit(OVERFLOW);
   p = L->head;
   for (i=0; ss[i]; i++) {
      if (!(p->next = (NLink)malloc(sizeof(NLNode)))) exit(OVERFLOW);
      p = p->next;   p->data = ss[i];
   }
   L->tail = p;   p->next = NULL;   L->len  = i;
   return L;
}

Status ListInsert(NLinkList L, int i, ElemType e) {     
   Position p;
   if (!L || !L->head || i<1) return ERROR;       
   if (!(p = LocatePos(L, i-1))) return ERROR;    
   InsAfter(L, &p, MakeNode(e));                   
   return OK;
}

ElemType ListDelete(NLinkList L, int i) {   
   NLink p, s;   ElemType e;
   if (!L || !L->head || i<1) return nullE;         
   if (!(p = LocatePos(L, i-1))) return nullE;      
   if (p = DelAfter(L, p)) { e = p->data;   free(p);   return e; }  
   return errV;                                          
}

NLinkList MergeList(NLinkList La, NLinkList Lb, int (*compare)(ElemType, ElemType)) {        
   if (!La || !Lb) return NULL;               
   NLinkList Lc = InitList();                 
   NLink ha = GetHead(La), hb =GetHead(Lb);       
   NLink pa = NextPos(La,ha), pb=NextPos(Lb,hb);  
   while (pa && pb) {                            
      ElemType a = GetCurElem(pa), b = GetCurElem(pb);
      if (compare(a, b) <= 0)     
         { AppendOne(Lc, DelAfter(La, ha));   pa = NextPos(La, ha); }
      else                            
         { AppendOne(Lc, DelAfter(Lb, hb));   pb = NextPos(Lb, hb); }
   }//while
   if (pa) Append(Lc, pa);           
   else Append(Lc, pb);              
   free(ha);   free(hb);             
   free(La);   free(Lb);             
   return Lc;
}

void TravelNLList(NLinkList L, char* sa) { 
   int i ;   NLink p;
   p = L->head->next;   i = 0;   sa[0] = '(';
   while (p != NULL) {
      sa[++i] = p->data;
      p = p->next;
   }
   sa[++i] = ')';  sa[i+1] = '\0';
}

void printNLList(NLinkList L) {  
   NLink p = L->head->next;
   printf("(");   if (!p) { printf(")\n");   return; }
   printf("%c", p->data);   p=p->next;
   while (p!=NULL && p!=L) { printf(", %c", p->data);  p=p->next; }
   printf(")\n");
}