Leetcode 147. Insertion Sort List

/**
 * 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 || !head->next) {
            return head;
        }
        ListNode* list = head;
        ListNode* current = head->next;
        ListNode* next = nullptr;
        head->next = nullptr;
        while(current != nullptr) {
            next = current->next;
            list = insert(list, current);
            current = next;
        }
        return list;
    }

private:
    ListNode* insert(ListNode* head, ListNode* node) {
        node->next = nullptr;
        if(head->val >= node->val) {
            node->next = head;
            return node;
        }
        ListNode* pre = head;
        ListNode* current = head->next;
        while(current) {
            if(current->val > node->val) {
                break;
            }
            pre = current;
            current = current->next;
        }
        pre->next = node;
        node->next = current;
        return head;
    }
};