Sort With Optimization


  • 0
    O

    A sort with optimization, so if the list is already sorted then only one pass is required.

            if (null == head){
                return null;
            }
    
            ListNode prev = head;
            ListNode cur = head.next;
    
            while (null != cur){
                if (prev.val < cur.val){
                    prev = cur;
                    cur = cur.next;
                }else {
                    ListNode pa = null;
                    ListNode a = head;
                    while (a != cur){
                        if (a.val < cur.val){
                            pa = a;
                            a = a.next;
                        }else {
                            ListNode nxt = cur.next;
                            if (null == pa){
                                head = cur;
                                pa = cur;
                            }else {
                                pa.next = cur;
                            }
                            cur.next  = a;
                            prev.next = nxt;
                            cur = nxt;
                            break;
                        }
                    }
                }
            }
    
    ```>! [Spoiler](link url)

Log in to reply
 

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