Java 31ms Beat 81%


  • 0
    V

    Same principle as insertion sort: sorted list at the front, and comparing them from front as its not a doubly linked list.
    I keep track of the end of the sorted list at front, and change if necessary.

    public ListNode insertionSortList(ListNode head) 
    {
        if(head == null || head.next == null)
            return head;
        ListNode curr = head.next, first = head, temp, fprev = null, endList = head;
        while(curr != null)
        {
            temp = curr.next;
            while(first != curr)
            {
                if(curr.val < first.val)
                {
                    if(fprev != null)
                        fprev.next = curr;
                    curr.next = first;
                    if(first == head)
                        head = curr;
                    break;
                }
                fprev = first;
                first = first.next;
            }
            if(first == curr)
                endList = first;
            endList.next = temp;                
            first = head;
            curr = temp;
            fprev = null;
        }
        return head;
    }

Log in to reply
 

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