本文共 957 字，大约阅读时间需要 3 分钟。

题目：

解答：

千万不要给链表插入排序啊  真TM的麻烦

先从链表中删除一个节点  然后把被删除节点插入到链表中，关键判断什么时候更新链表的有序尾。。。

代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:	ListNode *tail;	ListNode *insertionSortList(ListNode *head) {		if (head == NULL)			return head;		tail = head;		while(tail->next != NULL)		{			ListNode *node = tail->next;			tail->next = tail->next->next;			head = insert(head, node);		}		return head;	}	ListNode* insert(ListNode *head, ListNode *node)	{		if (node->val <= head->val)		{			node->next = head;			head = node;		}		else		{			ListNode *temp = head;			while (1)			{				if ((temp == tail) ||(temp->val < node->val && temp->next->val >= node->val))				{					node->next = temp->next;					temp->next = node;

					//特别注意在这里更新尾部					if (temp == tail)						tail = node;					break;				}				else				{					temp = temp->next;				}			}		}		return head;	}	};

转载地址：http://uutsi.baihongyu.com/