LeetCode| sort list 单链表的归并排序

Sort a linked list in O(n log n) time using constant space complexity.

看到O(n log n)的排序算法，适合单链表的首先想到的就是归并排序

达到这个复杂度的排序算法，对于单链表来说，最合适的就是

 <pre name="code" class="cpp">#include <iostream>
#include <vector>
using namespace std;
/*
对于链表的排序  使用归并排序最合适 
*/
typedef struct list_node List;
struct list_node
{
	struct list_node* next;
	int value;
};

void print_list(List* list)
{
	List* tmp=list;
	while(tmp != NULL)
	{
		cout<<tmp->value<<endl;
		tmp = tmp->next; 
	}
}

/*
初始化List  将从1~n的数字插入到链表中 
*/
void Init_List(List*& head,int* array,int n)
{
	head = NULL;
	List* tmp;
	List* record;
 	for(int i=1;i<=n;i++)
	{
		tmp = new List;
		tmp->next = NULL;
		tmp->value = array[i-1];
		if(head == NULL)
		{
			head = tmp;
			record = head;
		}
		else
		{
			record->next = tmp;
			record = tmp;
		}
	}
}

int Len_list(List* list)
{
	if(list == NULL)
		return 0;
	else
		return Len_list(list->next)+1;
}
/*
对于平常的merge操作 采用的分治方法 先分开然后再合并 
*/

void FindMid(List*& list,List*& pre,List*& last)
{
	pre  = list;
	last = list->next;
	while(last != NULL && last->next != NULL)
	{
		pre = pre->next;
		last = last->next;
		if(last->next != NULL)
			last = last->next;			
	}
	last = pre->next;
	pre->next  = NULL;
	pre = list;
}
void Merge(List*& list,List*& pre,List*& last)
{
	if(pre == NULL)
	{
		list = last;
		return ;
	}
	if(last == NULL)
	{
		list = pre;
		return ;
	}
	List* cur;
	List* tmp;
	
	if(pre->value > last->value)
		swap(pre,last);
	list = pre;
	cur = pre;
	while(cur->next != NULL && last != NULL)
	{
		if(cur->next->value > last->value)  //插入元素
		{
			tmp = last->next;
			last->next = cur->next;
			cur->next = last;
			cur = last;
			last = tmp;
		}
		else
			cur = cur->next; 
	}
	if(last != NULL)
	 cur->next = last;
}

void Merge_sec(List*& list,List*& pre,List*& last)
{
	
	List* tmp = new List;
	list = tmp;
	while(pre != NULL && last != NULL)
	{
		if(pre->value < last->value)
		{
			tmp->next = pre;
			pre = pre->next;
		} 
		else
		{
			tmp->next = last;
			last = last->next;
		}
	 
		tmp = tmp->next;
	}
	if(last != NULL)
		tmp->next = last;
	else
		tmp->next = pre;
	list = list->next;
 
} 

void MergeSort(List*& list)
{
	if(list ==NULL || list->next == NULL)
		return ;
	List* pre=NULL;
	List* last=NULL;
	FindMid(list,pre,last); //找到中间点 将一个链表list从中间分成pre和last两部分 
 
	MergeSort(pre); //归并排序前半部分  
	MergeSort(last); //归并排序后半部分 
	Merge(list,pre,last); //将两部分的链表进行合并 
}

int main() 
{
	int array[]	={7,4,9,15,2,1,6,10,12,11};
	List* head;
	Init_List(head,array,sizeof(array)/sizeof(array[0]));
	MergeSort(head);
	print_list(head);
	return 0;
}

LeetCode| sort list 单链表的归并排序

原文：http://blog.csdn.net/yusiguyuan/article/details/44596523