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

// 链表
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int ElemType;
typedef int Status;


// 定义链表
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;


// 创建一个链表，已倒叙顺序插入键盘输入的数据
Status CreateList_L(LinkList &L);
// 把两个升序的链表合成一个升序的链表
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc);
// 获取链表的第i个元素
Status GetElem_L(LinkList L,int i,ElemType &e);
// 向L第i个位置前插入数据
Status ListInsert_L(LinkList &L,int i,ElemType e);
// 删除L的第i个位置的元素，并赋给e
Status ListDelete_L(LinkList &L,int i,ElemType e);
// 输出所有的节点
void ShowList(LinkList L);
ElemType GetElem_L(LinkList L, int i);


// 创建一个链表
Status CreateList_L(LinkList &L){
	L = (LinkList)malloc(sizeof(LNode));
	if(!L) exit(OVERFLOW);
	L->next = NULL;
	return OK;
}
// 获取链表的第i个元素
Status GetElem_L(LinkList L,int i,ElemType &e){
	int j=1;
	LinkList p = L->next;
	while(p && j<i){
		p=p->next;
		j++;
	}
	if(!p || j>i) return ERROR;
	e = p->data;
	return OK;
}
// 在L的第i个位置前插入e
Status ListInsert_L(LinkList &L,int i,ElemType e){
	LinkList q,p;
	if(i<1) return ERROR;
	q = (LinkList)malloc(sizeof(LNode));
	q->data = e;
	if(!q) exit(OVERFLOW);
	// 查找第i-1个元素
	p = L;
	while(--i && p){
		p=p->next;
	}
	if(!p) return ERROR;
	q->next = p->next;
	p->next = q;
	return OK;
}
// 删除L的第i个位置的元素，并赋给e
Status ListDelete_L(LinkList &L,int i,ElemType e){
	LinkList q,p;
	if(i<1) return ERROR;
	p = L;
	while(--i && p){
		p=p->next;
	}
	q = p->next;
	if(!q) return ERROR;
	p->next = q->next;
	free(q);
	return OK;
}

// 把两个升序的链表合成一个升序的链表
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
	LinkList pa,pb,pc;
	// 去除根节点
	pa = La->next;pb = Lb->next;
	// 选取a根节点为c的根节点
	Lc = pc = La;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa?pa:pb;
	// 去除b的头结点
	free(Lb);
}

void ShowList(LinkList L){
	// 去除头结点
	for (int i = 1; i < 100; ++i)
	{
		if(!GetElem_L(L,i)){
			break;
		}
		printf("%d\n",GetElem_L(L,i) );
	}
}
ElemType GetElem_L(LinkList L, int i){
	if(i<1) return ERROR;
	while(i-- && L){
		L=L->next;
	}
	if(!L) return ERROR;
	return L->data;
}