LeetCode之Sort List

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

对一个单链表进行排序，要求时间复杂度为O(n log n)，空间复杂度为常量

分析：在排序中高速排序，堆排序，归并排序等都是能够在O(n log n)的时间复杂度之内完毕的。

a) 高速排序能够进行空间复杂度为1的原地排序，但必须是在能够反向索引的情况下。比如通过下标的减法向前索引。或者通过双向指针进行索引(双向链表)。

b) 堆排序必需要大小为n的额外空间，不考虑。

c) 归并排序理论上也是须要n的额外空间的(合并的时候)，可是考虑到此次是链表的特殊情况。能够借助链表的插入这样的方式进行破坏性的操作来达到排序的目的。即不改变每一个节点中的元素，每次到合并的时候就通过改动next指针又一次组成一条新的链表。终于达到常量空间O(n log n)时间的单链表排序，详细细节见代码。

代码例如以下：

在leetcode中提交时。仅仅需拷贝class中的函数就可以，此处完整的cpp文件是为了更好的模拟运行过程

#include<iostream>
using namespace std;

//Sort a linked list in O(n log n) time using constant space complexity.
//尝试使用归并排序，待排序元素为单链表
struct ListNode {
	int val;
	ListNode *next;
};

class Solution {
public:
	ListNode *sortList(ListNode *head) 
	{
		ListNode * retHead = NULL;
		int listLen = GetLen(head);
		if (listLen < 2)
		{
			return head;
		}
		retHead = MergeSort(head,listLen);
		return retHead;

	}

	//获取距离head长度为len-1距离的节点指针
	ListNode* GetMid(ListNode*head , int len)
	{
		ListNode *temp = head;
		for (int i = 1; i< len; i++)
		{
			head = head->next;
		}
		return head;
	}

	//归并排序
	ListNode* MergeSort(ListNode* head, int len)
	{
		if (len == 1)
		{
			return head;
		}
		int mid = len/2;
		ListNode *secondHead = GetMid(head, mid+1);         
		head = MergeSort(head, mid);
		secondHead = MergeSort(secondHead,len-mid);
		head = CombinList(head,mid,secondHead,len-mid);
		return head;
	}

	//为了降低储存空间，仅仅有破坏链表的原有结构,重组链表达到排序的目的
	ListNode* CombinList(ListNode *pList1,int len1, ListNode* pList2,int len2)
	{
		int sum = len1+len2;
		ListNode* retHead = NULL;
		ListNode* retTail = NULL;
		ListNode* nextLink = GetMid(pList2,len2+1);   //指向下一条链表的头结点
		ListNode * exList = NULL;  //用于指向交互结点的指针

		if (pList1->val > pList2->val)             //确定返回的头结点
		{
			retHead = pList2;
			pList2 = pList2->next;
			len2--;
		}
		else
		{
			retHead = pList1;
			pList1 = pList1->next;
			len1--;

		}
		retTail = retHead;
		while (len1 != 0 && len2 != 0)
		{
			if (pList1->val > pList2->val)
			{
				retTail->next = pList2;
				retTail= retTail->next;
				pList2 = pList2->next;
				len2--;
			}
			else
			{
				retTail->next = pList1;
				retTail=retTail->next;
				pList1 = pList1->next;
				len1--;
			}
		}

		if (len1 == 0)
		{
			retTail->next = pList2;
		}
		else
		{
			retTail->next = pList1;
			while (len1 > 1)
			{
				pList1= pList1->next;
				len1--;
			}
			pList1->next = nextLink;
		}
		return retHead;
	}


	//获取链表的长度,时间复杂度为n
	int GetLen(ListNode *head)
	{
		int len = 0;
		while (head!=NULL)
		{
			len++;
			head = head->next;
		}
		return len;
	}
};

void printList(ListNode* head)
{
	cout<<endl;
	while (head != NULL)
	{
		cout<<head->val<<" ";
		head=head->next;

	}
	cout<<endl;
}
int main()
{
	ListNode *head = new ListNode;
	ListNode *tail = head;
	head->val = 4;
	head->next = NULL;
	for (int i = 0; i< 19; i++)
	{
		ListNode* temp = new ListNode;
		temp->val = rand()%90;
		temp->next = NULL;
		tail->next = temp;
		tail = tail->next;
	}
	printList(head);
	Solution a;
	head = a.sortList(head);
	printList(head);
	system("pause");
	return 0;
}

模拟排序前后结果为：