L147. Insertion Sort List

LinkedList

Problem:

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Solution:

• TC: n^2;

• two pointers, first check cur != null; next find the location to insert (last index less than cur)

• the list is always divided by 2 lists.

  • pre -> (already sorted) and

  • cur -> (not sorted).

• when pre is dummy, it doesn't has ->;

After 1st loop,

pre -> 6 -> null

5 -> 3 -> 1 -> 8 -> 7

• cur.next = pre.next // 5 ->6

• pre.next = cur // pre -> 5 instead 6

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode pre = dummy;
    ListNode current = head;

    while(current!= null) {
        pre = dummy;
        while(pre.next !=null && pre.next.val < current.val) {
                pre =pre.next;
            }
        ListNode next = current.next;
        current.next = pre.next;
        pre.next = current;
        current = next;
    }
    return dummy.next;
    }