147 Insertion Sort List

Posted on | In

Intuition & Algorithm

The diagram and illustration in the question have given us a clear description of insertion sort algorithm.

  1. Separate the list into two parts: sorted and sorting
  2. Insert the head of sorting list into the sorted list

We should consider three cases during insertion(v is the node to be inserted):

  • v < sorted.head.val we should use this node as the new head of sorted list
  • cur.val < v < cur.next.val cur is a node in the sorted list, in this case we should insert the new node between cur and cur.next
  • cur.next == null this means v is large than any number in the list, so we append it to the tail.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null)return head;
        ListNode sorted=head,sorting = head.next, next;
        head.next = null;
        while(sorting != null){
            next = sorting.next;
            
            ListNode cur = sorted;
            if(sorting.val < cur.val){
                sorting.next = sorted;
                sorted = sorting;
            }
            else{
                while(cur.next != null){
                    if(sorting.val >= cur.val && sorting.val <= cur.next.val)
                    {
                        sorting.next = cur.next;
                        cur.next = sorting;
                        break;
                    }
                    cur = cur.next;
                }
                if(cur.next == null){
                    sorting.next = null;
                    cur.next = sorting;
                }
            }
            sorting = next;
        }
        return sorted;
    }
}

Complexity

Time Complexity: $O(n)$

Spatial Complexity: $O(1)$