/*归并法：用于合并两个链表*/

/*
* SCs in different cases
* author: Whywait
*/

typedef struct node {
	Elemtype data;
	struct node* next;
} Lnode;

/*case ONE*/

Lnode* merge1(Linklist& LA, Linklist& LB) {
	// merge two sorted Singly linked lists
	// LA, LB and the return one ( LC ) all have a head node
	// all the linklist are sorted in the same way: increasing or decreasing
	// we assume that all the slists are sorted in an increasing order
	// KEY: insert in the tail

	Lnode* LC = (Lnode*)malloc(sizeof(Lnode));
	LC->next = NULL;
	Lnode* pa = LA->next, * pb = LB->next, * pc = LC;

	while (pa && pb) { 
		if (pa->data < pb->data) {
			pc->next = pa;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pb = pb->next;
		}
		pc = pc->next;
	}

	if (pa) pc->next = pa;
	if (pb) pc->next = pb;
	return LC;
}

/*case TWO*/

Lnode* merge2(Linklist& LA, Linklist& LB) {
	// merge two sorted Singly linked lists
	// LA, LB and the return one ( LC ) all have a head node
	// all the linklist are sorted not in the same way: 
	//		LA and LB are the same, but LC just the other way
	// we assume that LA and LB are sorted in an increasing order
	// KEY: insert in the front

	Lnode* LC = (Lnode*)malloc(sizeof(Lnode));
	LC->next = NULL;
	Lnode* pa = LA->next, * pb = LB->next;

	while (pa && pb) {
		Lnode* temp = NULL;
		if (pa->data < pb->data) {
			temp = pa->next;
			pa->next = LC->next;
			LC->next = pa;
			pa = temp;
		}
		else {
			temp = pb->next;
			pb->next = LC->next;
			LC->next = pb;
			pb = temp;
		}
	}

	if (pa) pc->next = pa;
	if (pb) pc->next = pb;
	return LC;
}