LeetCode--Insertion Sort List

Sort a linked list using insertion sort.

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

LeetCode--Insertion Sort List

原文：http://blog.csdn.net/shaya118/article/details/42741003