147. Insertion Sort List

// LeetCode URL: https://leetcode.com/problems/insertion-sort-list/
//  Definition for singly-linked list.
// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int x) {
//         val = x;
//     }
// }

/**
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input list.
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode dummySorted = new ListNode(-1);
        ListNode curr = head;
        ListNode prevSorted = dummySorted;

        while (curr != null) {
            ListNode next = curr.next;

            // This will only reset prevSorted to dummySorted only if the current prevSorted
            // is greater than curr node.
            if (curr.val < prevSorted.val) {
                prevSorted = dummySorted;
            }

            while (prevSorted.next != null && curr.val > prevSorted.next.val) {
                prevSorted = prevSorted.next;
            }

            curr.next = prevSorted.next;
            prevSorted.next = curr;

            curr = next;
        }

        return dummySorted.next;
    }
}