/ Data Structure and Algorithms  

Leetcode 147. Insertion Sort List

Question



Implement insertion sorting based on linked lists.

Similar Questions

Solution

The so-called insertion sorting is to take one number at a time and insert it to the correct position.

For exampel:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4 2 1 3
res = []

Take 4
res = [4]

Take 2
res = [2 4]

Take 1
res = [1 2 4] 

Take 3
res = [1 2 3 4]

To implement it, because we want to take out an element from the linked list that we want to insert it into the sorted list, we must first traverse the sorted list, find the first position that is larger than the element to be inserted, and insert the element in front.

As for insertion, we need to know the node before the insertion position, so we can use node.next to compare with the node to be inserted, node is the node before the insertion position.

The head pointer is already at the forefront, so we can use a dummy pointer to unify the situation of the head pointer.

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
42
43
44
45
46
47
public ListNode insertionSortList(ListNode head) {
    // if input list has no element return null
    if (head == null) {
        return null;
    }

    // create a dummyHead, the node before the actual head
    ListNode dummyHead = new ListNode(0);

    // current node
    ListNode current = head;

    // loop original list
    while (current != null) {
        ListNode temp = dummyHead;
        // need this temp to record the next of current
        final ListNode currentNext = current.next;

        // set current.next to null as we don't want to move everything after current
        current.next = null;

        // find the node in the result that is greater than current node
        while (temp.next != null) {
            if (temp.next.val > current.val) {
                // move the head from original to the result
                current.next = temp.next;
                temp.next = current;

                // find the spot for this node, move to next
                break;
            }

            // check next in result
            temp = temp.next;
        }

        // didn't find, mean current greater than all in the result
        if (temp.next == null) {
            temp.next = current;
        }

        // move current node
        current = currentNext;
    }

    return dummyHead.next;
}