7ms Java solution with explanation

  • 17

    The only real modification here is to take advantage of the ability to add to both the front and end of a linked list in constant time. A typical insertion sort would have to go through the entire array to find the new location to insert the element. If the element should be placed first in the array then we have to shift everything over. Thankfully, with a linked list we don't need to do this. The slight modification of keeping a pointer to the last node as well as the first dramatically increased the runtime of the algorithm. That being said, the speedup still has a lot to do with the ordering if the items in the array.

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode sortedHead = head, sortedTail = head;
        head = head.next;
        sortedHead.next = null;
        while (head != null)
            ListNode temp = head;
            head = head.next;
            temp.next = null;
            // new val is less than the head, just insert in the front
            if (temp.val <= sortedHead.val)
                temp.next = sortedHead;
                sortedTail = sortedHead.next == null ? sortedHead : sortedTail;
                sortedHead = temp;
            // new val is greater than the tail, just insert at the back
            else if (temp.val >= sortedTail.val)
                sortedTail.next = temp;
                sortedTail = sortedTail.next;
            // new val is somewhere in the middle, we will have to find its proper
            // location.
                ListNode current = sortedHead;
                while (current.next != null && current.next.val < temp.val)
                    current = current.next;
                temp.next = current.next;
                current.next = temp;
        return sortedHead;

  • 1

    @bdwalker I have upvoted your solution. I think the space complexity is O(n), since you are creating a new temp node for every head. And for insertion sort the worst case would be when all the elements are in decreasing order. So time complexity of your algorithm is also O(n), since you are handling addition at head and tail pretty well. Let me know if the complexities are correct. Thanks.

  • 0

    Thanks for sharing the excellent code.
    I removed one line:
    sortedTail = sortedHead.next == null ? sortedHead : sortedTail;
    and still passed the case.
    It seems to me that if the temp is less than the sortedHead, the sortedTail may not be affected?

Log in to reply

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