#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*問題:Sort a linked list using insertion sort.分析:用插入排序?qū)σ粋€鏈表排序。插入排序：數(shù)組A分成A[1..i],A[i+1...n]其中數(shù)組前面部分已經(jīng)有序，選擇當(dāng)前元素，從有序部分后面向前查找到當(dāng)前元素可以插入的位置進(jìn)行插入。將該位置之后的節(jié)點都往后移。如果對鏈表插入排序，可以將每個節(jié)點存儲在數(shù)組中，轉(zhuǎn)化為對數(shù)組的比較，注意頭結(jié)點可能發(fā)生變化。尋找插入位置的時候，可以采用二分法來減少查找時間。輸入:5(數(shù)組元素個數(shù))1 5 4 6 355 1 4 6 3輸出:1 3 4 5 61 3 4 5 6關(guān)鍵:1 找到插入的位置要立即break；如果沒有找到插入位置，說明當(dāng)前待插入元素是最小的要插入在頭部*/struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    ListNode* insertionSortList(ListNode* head) {        if(!head)		{			return NULL;		}		vector<ListNode*> nodes;		ListNode* node = head;		while(node)		{			nodes.push_back(node);			node = node->next;		}		int size = nodes.size();		//與頭結(jié)點比較		int j;		for(int i = 0 ; i < size - 1; i++)		{			//當(dāng)前待比較節(jié)點的值			ListNode* curNode = nodes.at(i+1);			ListNode* nextNode = NULL;			int value = curNode->val;			for(j = i; j >= 0 ; j--)			{				//如果當(dāng)前節(jié)點的值 <= 給定值，找到待插入位置j+1,將j+1到i的所有元素后移一位				if(nodes.at(j)->val <= value)				{					if(nodes.at(j+1))					{						nextNode = nodes.at(j+1);					}					//先移動數(shù)組位置					for(int k = i ; k >= j + 1 ; k--)					{						nodes.at(k+1) = nodes.at(k);					}					nodes.at(j+1) = curNode;					//并最好連同數(shù)組位置也需要交換，因為之后就是根據(jù)數(shù)組位置來比較的					nodes.at(j)->next =curNode;					if(curNode != nextNode)					{						curNode->next = nextNode;					}					break;//第一次找到后就退出				}			}			//當(dāng)前節(jié)點最小，需要作為首節(jié)點			if(j < 0)			{				nextNode = nodes.at(0);				//先移動數(shù)組位置				for(int k = i ; k >= 0 ; k--)				{					nodes.at(k+1) = nodes.at(k);				}				nodes.at(0) = curNode;				if(curNode != nextNode)				{					curNode->next = nextNode;				}			}		}		//設(shè)置尾節(jié)點指向空		nodes.at(size - 1)->next = NULL;		return nodes.at(0);//頭結(jié)點為根節(jié)點    }};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.insertionSortList(head);		 print(newHead);		 deleteList(newHead);//刪除節(jié)點了	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}