LeetCode: Insertion Sort List

Sort a linked list using insertion sort.

---

Just do it like sorting an array. And for linked list, it is easier to move nodes. Split the linked list into two parts. One is sorted, and the other one is unsorted. Each time find an insertion position for the current node.

C++ Code:

/*
 * func: find_insertion_position
 * goal: find the insertion position for insertion sort
 * @param head: head node
 * @param move: the node needed to be inserted
 * return: the node before the insertion position
 */
ListNode *find_insertion_position(ListNode *head, ListNode *move){
    while(head->next && head->next->val <= move->val){
        head = head->next;
    }
    return head;
}

/*
 * func: insertion_sort
 * goal: insertion sort linked list
 * @param head: head node
 * return: new head node
 */
ListNode *insertion_sort(ListNode *head){
    if(head == nullptr || head->next == nullptr){
        return head;
    }
    ListNode *iter = head;
    ListNode *sentinal = new ListNode(numeric_limits<int>::min());
    while(iter){
        ListNode *next = iter->next;
        
        ListNode *insert_pos = find_insertion_position(sentinal, iter);
        iter->next = insert_pos->next;
        insert_pos->next = iter;
        iter = next;
    }
    return sentinal->next;
}

Python Code:

# func: insertion sort for linked list
# @param head: head node of the linked list
# @return: new head node
def insertion_sort(head):
    def find_insertion_position(new_head, curr):
        while new_head and curr.val > new_head.val:
            new_head = new_head.next
        return new_head

    if not head or not head.next:
        return head
    iter = head
    while iter.next:
        next = iter.next
        #If current value is greater than the previous one, move forward
        if next.val >= iter.val:
            iter = iter.next
            continue
        #Get current node out the link list
        iter.next = next.next
        #Find a inserting position
        if next.val <= head.val:
            next.next = head
            head = next
            continue

        insert_position = find_insertion_position(head, next)

        next.next = insert_position.next
        insert_position.next = next

    return head

Reference Link:

1. LeetCode — Insertion Sort List（C++ Java Python） - 龙之梦 - 博客频道 - CSDN.NET: http://blog.csdn.net/lilong_dream/article/details/20070531

2. [LeetCode] Insertion Sort List | Xiaopeng Xu's Blog: http://xpxu.net/blog/?p=83