#ifndef _List_H
#define _List_H

typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty();
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
void Print(List L);
void PrintByAnotherList(List L, List P);
List AddTwoList(List L, List L2);
//Position Header(List L);
//Position Advance(Position P);
//ElementType Retrieve(Position P);

#endif



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

struct Node
{
	ElementType Element;
	struct Node *Next;
};

List MakeEmpty()
{
	List Header = (List)malloc(sizeof(struct Node));
	Header->Next = NULL;
	return Header;
}

int IsEmpty(List L)
{
	return L->Next == NULL;
}

int IsLast(Position P, List L)
{
	return P->Next == NULL;
}

Position Find(ElementType X, List L)
{
	Position P;
	P = L->Next;
	
	while(P != NULL && X != P->Element)
	{
		P = P->Next;
	}

	return P;
}

void Delete(ElementType X, List L)
{
	Position Pre, TmpCell;

	Pre = FindPrevious(X, L);

	if(!IsLast(Pre, L))
	{
		TmpCell = Pre->Next;
		Pre->Next = TmpCell->Next;
		free(TmpCell);
	}
}

Position FindPrevious(ElementType X, List L)
{
	Position Pre;
	Position P;

	Pre = L;
	P = Pre->Next;
	
	while(P != NULL && X != P->Element)
	{
		Pre = P;
		P = P->Next;
	}

	return Pre;
}

void Insert(ElementType X, List L, Position P)
{
	Position TmpCell;
	
	TmpCell = (Position)malloc(sizeof(struct Node));
	if(TmpCell == NULL)
	{
		printf("Out of space!!!");
		return;
	}
	TmpCell->Element = X;
	TmpCell->Next = P->Next;
	P->Next = TmpCell;
}

void DeleteList(List L)
{
	Position TmpCell, P;
	
	P = L->Next;
	L->Next = NULL;
	while(P != NULL)
	{
		TmpCell = P->Next;
		free(P);
		P = TmpCell;
	}
}

void Print(List L)
{
	Position P = L->Next;
	while(P != NULL)
	{
		printf("%d\t", P->Element);
		P = P->Next;
	}
	printf("\n");
}

/*
*L链表和P链表都已经排好序
*/
void PrintByAnotherList(List L, List P)
{
	int i;
	Position CurrP;
	Position NextP;
	Position WorkingPositionInL = L;
	ElementType SaveP;
	
	SaveP = P->Element;
	P->Element = 0;
	CurrP = P;
	NextP = CurrP->Next;
	
	while(NextP != NULL)
	{
		for(i = CurrP->Element; i < NextP->Element; i++)
		{
			WorkingPositionInL = WorkingPositionInL->Next;
		}
		printf("%d\t", WorkingPositionInL->Element);
		CurrP = NextP;
		NextP = NextP->Next;
	}
	printf("\n");

	P->Element = SaveP;
}

/*
*有序链表merge
*/
List AddTwoList(List L1, List L2)
{
	int count1 = 0, count2 = 0;
	Position P1 = L1->Next;
	Position SaveL1Last = L1;
	Position P2 = L2->Next;
	Position SaveL2Last = L2;
	Position TempCell;
	Position WorkingCell;
	
	while(P1 != NULL)
	{
		count1++;
		SaveL1Last = P1;
		P1 = P1->Next;
	}

	while(P2 != NULL)
	{
		count2++;
		SaveL2Last = P2;
		P2 = P2->Next;
	}

	if(count1 < count2)
	{
		P1 = L1->Next;
		P2 = L2;

		//链表头需另外处理
		if(L2->Next->Element > L1->Next->Element)
		{
			printf("======================\n");
			TempCell = (Position)malloc(sizeof(struct Node));
			TempCell->Element = L1->Next->Element;
			TempCell->Next = NULL;
			TempCell->Next = L2->Next;
			L2->Next = TempCell;
			P1 = P1->Next;
			P2 = TempCell;
		}

		while(P1 != NULL)
		{
			TempCell = (Position)malloc(sizeof(struct Node));
			TempCell->Element = P1->Element;
			TempCell->Next = NULL;
			
			while(P2 != NULL && P2->Element < P1->Element)
			{
				WorkingCell = P2;
				P2 = P2->Next;
			}
			TempCell->Next = P2;
			WorkingCell->Next = TempCell;
			P1 = P1->Next;
		}
		return L2;
	}
	else
	{
		return L1;
	}
}

//Position Header(List L);
//Position Advance(Position P);
//ElementType Retrieve(Position P);



#include <stdio.h>
#include "ListADT.h"

int main()
{
	Position P;
	List M;
	List L = MakeEmpty();
	List W = MakeEmpty();
	
	Insert(1, L, L);
	P = Find(1, L);
	Insert(3, L, P);
	Print(L);

	Insert(2, W, W);
	P = Find(2, W);
	Insert(4, W, P);
	P = Find(4, W);
	Insert(5, W, P);
	P = Find(5, W);
	Insert(6, W, P);
	Print(W);

	M = AddTwoList(L, W);
	Print(M);
	return 0;
}