#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;}