首页 > 代码库 > 链表的归并排序

链表的归并排序

        因为链表是节点式存储,不能做到随机存储,但是对于两个有序链表之间的合并不需要额外的空间,在O(1)空间复杂度O(n)时间复杂度内即可完成。所以对于链表排序,使用归并排序比较划算。

typedef struct Node List;
struct Node
{
       int value;
       List* next; 
       }; 

//链表节点结构体

首先合并两个有序的链表:

/*
	在合并的时候始终保持一个链表的节点插入另一个链表中
	这里始终保证first是最终的链表,将second链表中的每一个节点逐步插入到first中 
*/
List* Merge(List* first,List* second)
{
	List* head = NULL;
	List* current = NULL;
	if(first == NULL)
		return second;
	if(second == NULL)
		return first;
	 if(first->value > second->value)
	 {
	 	current = first;
	 	first = second;
	 	second = current;
	 }
	 head = first;
	 current = first;
	 first = first->next; 
	 
	//始终将second的节点插入到first链表中 
	while( first != NULL && second != NULL)
	{
		 List* temp  = NULL; 
		 if(first->value > second->value)
		 {
			temp = second->next;			
			current->next = second;
			second->next = first;
			current = second;
			second = temp;	
		 }
		 else
		 {
			current = first;
			first = first->next;
		 }		
	}
	if(first == NULL)
		current->next = second;
	return head;
}

上面的代码是合并两个有序的链表,始终将second的链表节点插入到first链表节点,所以second始终指向头节点。对于first节点,始终将被插入的节点插入到current节点的后面,如果对于second节点来说在first中没有找到合适的节点,那么就需要更新current和first节点位置。


链表归并排序的主要框架代码:

int List_length(List* list)
{
	int len=0;
	List* temp = NULL;
	temp= list;
	while(temp != NULL)
	{
		len++;
		temp = temp->next;
	}
	return len;
}

List* MergeSort(List* list,int size)
{
	
		if(size == 0 || size == 1)
			return list;
		List* middle = list;
		int i;
		for(i=1;i<size/2;i++)
			middle = middle->next;
	
		List* temp = middle->next;
		middle->next = NULL;
		middle = temp;
	
		List* left = MergeSort(list,i);
		List* right = MergeSort(middle,size-i);
		return Merge(right ,left);
	
	
}


链表的归并排序