leecode 解题总结：148. Sort List

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Sort a linked list in O(n log n) time using constant space complexity.分析：在O(NlogN)时间内使用常量空间对一个链表排序这个复杂度的只有：堆排序(O(1)空间)，快速排序(O(logN)空间)，归并排序(要O(1)空间)应该是堆排序或者归并排序。搞错了。归并排序时间复杂度是O(1)，只不过之前某些算法为了实现方便，开辟辅助数组，所以让我误以为时间复杂度为O(n)。其实归并排序两两拆分排序，后续四四拆分排序等。这里主要先要对链表分成两部分，对前半部分和后半部分分别递归，求出前半部分的头结点和后半部分的头结点。然后归并这两个链表。开辟一个辅助新节点，新节点每次指向两个链表的较小值结点，返回新链表的头部结点输入:4(链表节点个数)4 3 2 155 4 1 3 222 111输出:1 2 3 41 2 3 4 51 21关键:1 参考leecode解法:https://leetcode.com/PRoblems/sort-list/?tab=Solutions将链表分成左半部分和右半部分，设定一个新链表，链表结点指向左右不分中的较小值，返回新的链表头结点。其中将链表拆分成左右不分采用快慢指针的方式，当快指针为空，慢指针指向右边部分链表头结点，注意将慢指针前一个元素的后边指向NULL，否则后续遍历发生错误空间复杂度为O(1),时间复杂度为O(nlogn)*/struct ListNode {   int val;   ListNode *next;   ListNode(int x) : val(x), next(NULL) {} };class Solution {public:	//归并两个链表，采用一个新的链表，两讲个链表的较小值存储在里面	ListNode* mergeSort(ListNode* head1 , ListNode* head2)	{		//如果两个链表都为空，直接返回空		if(NULL == head1 && NULL == head2)		{			return NULL;		}		//判断链表中头部结点。并且链表中另一个头部为空		else if(head1 && NULL == head2)		{			return head1;		}		else if(head2 && NULL == head1)		{			return head2;		}		ListNode* head = new ListNode(-1);		ListNode* newHead = head;		bool isFirst = true;		while(head1 && head2)		{			if(head1->val < head2->val)			{				head->next = head1;				head1 = head1->next;			}			else			{				head->next = head2;				head2 = head2->next;			}			head = head->next;		}		while(head1)		{			head->next = head1;			head = head->next;			head1 = head1->next;		}		while(head2)		{			head->next = head2;			head = head->next;			head2 = head2->next;		}		//删除头结点		ListNode* node = newHead->next;		delete newHead;		newHead = node;		return newHead;	}	//归并排序：先划分成左右两个链表（注意前半部分链表需要另最后一个结点的指针指向空），然后递归排序，然后归并    ListNode* sortList(ListNode* head) {        //将链表划分成两部分，采用快慢指针，当快指针走到最后的时候，慢指针走到前半部分链表最后一个结点		//1->2->3->4,刚开始，快慢指针为1，慢2，快3，慢3，快空，则前部分为慢指针的结点的前面一个		//1->2->3->4->5,快慢1，慢2，快3，慢3，块5,结束，慢为3前面的结点2，要指向空，来拆分出前半部分链表		//1->2		if(!head)		{			return NULL;		}		//如果仅有一个结点无需处理，递归基		if(NULL == head->next)		{			return head;		}		ListNode* prev = NULL;		ListNode* slow = head;		ListNode* fast = head;		while(fast && fast->next)		{			prev = slow;			slow = slow->next;			fast = fast->next->next;		}		if(prev)		{			prev->next = NULL;//前半部分链表最后一个结点指向空，来拆分出链表，必须判空		}		ListNode* node1 = sortList(head);//计算另一个链表的起点		ListNode* node2 = sortList(slow);//slow为后半部分链表第一个结点		ListNode* resultHead = mergeSort(node1 , node2);		return resultHead;    }};void print(ListNode* head){	if(!head)	{		cout << "no result" << endl;	}	ListNode* tempHead = head;	while(head)	{		cout << head->val << " ";		head = head->next;	}	cout << endl;	head = tempHead;}ListNode* buildList(vector<int>& nums){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	ListNode* head ;	ListNode *tail;	ListNode* node;	for(int i = 0 ; i < size ; i++)	{		if(i)		{			node = new ListNode(nums.at(i));			tail->next = node;			tail = node;		}		else		{			head = new ListNode(nums.at(i));			tail = head;		}	}	return head;}void deleteList(ListNode* head){	ListNode* node;	while(head)	{		node = head->next;		delete head;		head = node;	}}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 ListNode* head = buildList(nums);		 ListNode* newHead = solution.sortList(head);		 print(newHead);		 deleteList(newHead);//删除节点了	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}