leecode 解题总结：147. Insertion Sort List

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Sort a linked list using insertion sort.分析:用插入排序对一个链表排序。插入排序：数组A分成A[1..i],A[i+1...n]其中数组前面部分已经有序，选择当前元素，从有序部分后面向前查找到当前元素可以插入的位置进行插入。将该位置之后的节点都往后移。如果对链表插入排序，可以将每个节点存储在数组中，转化为对数组的比较，注意头结点可能发生变化。寻找插入位置的时候，可以采用二分法来减少查找时间。输入:5(数组元素个数)1 5 4 6 355 1 4 6 3输出:1 3 4 5 61 3 4 5 6关键:1 找到插入的位置要立即break；如果没有找到插入位置，说明当前待插入元素是最小的要插入在头部*/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();		//与头结点比较		int j;		for(int i = 0 ; i < size - 1; i++)		{			//当前待比较节点的值			ListNode* curNode = nodes.at(i+1);			ListNode* nextNode = NULL;			int value = curNode->val;			for(j = i; j >= 0 ; j--)			{				//如果当前节点的值 <= 给定值，找到待插入位置j+1,将j+1到i的所有元素后移一位				if(nodes.at(j)->val <= value)				{					if(nodes.at(j+1))					{						nextNode = nodes.at(j+1);					}					//先移动数组位置					for(int k = i ; k >= j + 1 ; k--)					{						nodes.at(k+1) = nodes.at(k);					}					nodes.at(j+1) = curNode;					//并最好连同数组位置也需要交换，因为之后就是根据数组位置来比较的					nodes.at(j)->next =curNode;					if(curNode != nextNode)					{						curNode->next = nextNode;					}					break;//第一次找到后就退出				}			}			//当前节点最小，需要作为首节点			if(j < 0)			{				nextNode = nodes.at(0);				//先移动数组位置				for(int k = i ; k >= 0 ; k--)				{					nodes.at(k+1) = nodes.at(k);				}				nodes.at(0) = curNode;				if(curNode != nextNode)				{					curNode->next = nextNode;				}			}		}		//设置尾节点指向空		nodes.at(size - 1)->next = NULL;		return nodes.at(0);//头结点为根节点    }};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);//删除节点了	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}