Insertion Sort List

Question (LC.147)

Sort a linked list using insertion sort.

Example

3 -> 2 -> 5 -> null
2 -> 3 -> 5 -> null

Analysis

Insertion Sort
dummy node

for each node in the linked list
    insert the node into the sorted position
end for

return dummy.next;

Insert
stop when the next node.value > newNode.value
Node temp = travel.next;
travel.next = newNode;
newNode.next = temp;

Code

public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    ListNode travel = head;

    while (travel != null) {
        ListNode temp = travel.next;
        insert(dummy, travel);
        travel = temp;
    }

    return dummy.next;
}

// assume head is not null
private void insert(ListNode head, ListNode newNode) {
    ListNode travel = head;

    while (travel.next != null && travel.next.val < newNode.val) {
        travel = travel.next;
    }

    ListNode temp = travel.next;
    travel.next = newNode;
    newNode.next = temp;
}