Java concise solution. O(1) space.


  • 0
    A

    Welcome to check my blog.
    Create a dummyHead. Move the element in head into dummyHead list one by one.

    public static ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        while (head != null) {
            // take out head to curr. head move to next
            ListNode curr = head;
            head = head.next;
            // put curr to target position in dummyHead. Put curr between target and target.next
            ListNode target = dummyHead;
            while (target.next != null && target.next.val < curr.val) {
                target = target.next;
            }
            curr.next = target.next;
            target.next = curr;
        }
        return dummyHead.next;
    }
    

    alt text


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.