学步园

            主要思路：

               1   如果为NULL或者只有一个节点那么直接返回；

               2    将链表分成两部分，分别进行排序，形成两个有序链表；

               3   将两个有序链表合并；

void merge_sort(struct Node **list)
{
	struct Node *p = *list;
	struct Node *left = NULL;
	struct Node *right = NULL;

	if (p == NULL || p->next == NULL)
		return ;
	split(p, &left, &right);
	merge_sort(&left);
	merge_sort(&right);

	*list = mergeSortedLink(left, right);
}



void split(struct Node *head, struct Node **listA, struct Node **listB) 
{
	
	if (head == NULL || head->next == NULL) {
		*listA = head;;
		*listB = NULL;
		return ;
	}
	struct Node *p = head;;
	struct Node *pfast = p->next;
	while (pfast->next != NULL) {
		pfast = pfast->next;
		if (pfast->next != NULL) {
			pfast = pfast->next;
			p = p->next;
		}
	}
	*listA = head;
	*listB = p->next;
	p->next = NULL;
}

struct Node *mergeSortedLink(struct Node *listA, struct Node *listB)
{
	struct Node *head = NULL;
	struct Node *tail = NULL;
	if (listA == NULL) {
		head = listB;
	} else if (listB == NULL) {
		head = listA;
	} else {
	while (listA != NULL && listB != NULL) {
		if (listA->data < listB->data) {
			if (head == NULL) {
				head = listA;
				tail = listA;
			} else {
				tail->next = listA;
				tail = listA;
			}
				listA = listA->next;
		} else {
			if (head == NULL) {
				head = listB;
				tail = listB;
			}else {
				tail->next = listB;
				tail = listB;
			}
				listB = listB->next;
		}
	}
	if (listA != NULL) {
		tail->next = listA;
	}

	if (listB != NULL) {
		tail->next = listB;
	}
	}
	return head;
}