Insertion Sort List -- leetcode

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) {
        ListNode fake(0);
        while (head) {
            ListNode *runner = &fake;
            while (runner->next && runner->next->val < head->val)
                runner = runner->next;
            
            ListNode *bak = head->next;
            head->next = runner->next;
            runner->next = head;
            head = bak;
        }
        return fake.next;
    }
};

原文：http://blog.csdn.net/elton_xiao/article/details/46401459