题目描述：

Sort a linked list using insertion sort.

思路：在head之前插入一个假头结点，便于在head节点之前插值。遍历链表，对于每一个节点，在它前面的有序的节点中找到第一个比它大的节点，将它插到该节点的前面。链表遍历结束后即得到有序链表。

代码：

ListNode * Solution::insertionSortList(ListNode *head)
{
    if(head == NULL || head->next == NULL)
        return head;
    ListNode * fake_head = new ListNode(INT_MIN);
    fake_head->next = head;
    ListNode * left = head;
    ListNode * right = head;
    ListNode * left_pre = fake_head;
    ListNode * right_pre = fake_head;
    while(right != NULL)
    {
        left = fake_head->next;
        left_pre = fake_head;
        while(left != right)
        {
            if(left->val > right->val)
            {
                right_pre->next = right->next;
                right->next = left;
                left_pre->next = right;
                right = right_pre->next;
                break;
            }
            else
            {
                left = left->next;
                left_pre = left_pre->next;
            }
        }
        if(left == right)
        {
            right = right->next;
            right_pre = right_pre->next;
        }
    }
    return fake_head->next;
}

LeetCode:Insertion Sort List