LeetCode--148. Sort List

タイトルリンク:https://leetcode.com/problems/sort-list/
最初に思いついたのは、ノードを配列で保存してから速く並べて、簡単で乱暴です.

public ListNode sortList(ListNode head) {
    ListNode node = head;
    int cnt = 0;
    while (node != null) {
        cnt++;
        node = node.next;
    }
    int[] nums = new int[cnt];
    node = head;
    cnt = 0;
    while (node != null) {
        nums[cnt++] = node.val;
        node = node.next;
    }
    Arrays.sort(nums);
    node = head;
    cnt = 0;
    while (node != null) {
        node.val = nums[cnt++];
        node = node.next;
    }
    return head;
}

しかし、問題はO(nlogn)の時間的複雑さとO(1)空間的複雑さの下でソートを完了することを要求し、これはまず速列、集計、スタックソートのようなO(nlogn)の時間的複雑さのアルゴリズムを考え、またO(1)空間的複雑さの下でこの操作を完了することを要求し、そのスタックソートは絶対にだめである.速い列の再帰における2つのサブ配列の合併は,2つのサブ配列と歩哨の比較に基づいて実現され,配列の下標に厳格に依存し,チェーンテーブルに用いるのは非常に骨が折れる可能性がある.併合してみるしかない.
コードは配列の集計ソートと類似しており、集計ソートはこの詳細を参照してください.https://blog.csdn.net/To_be_to_thought/article/details/83988767を参照してください.https://blog.csdn.net/To_be_to_thought/article/details/85057542.
肝心なのはどのように切り分けるかです.ここでは、チェーンテーブル全体をほぼ等しい2つのサブチェーンテーブルに分けます.切り分けるコードは以下の通りです.

public ListNode sortList(ListNode head) {
        
        if(head==null || head.next==null)
            return head;
        //      1 return

        ListNode pFast=head,pSlow=head;
        while(pFast.next!=null && pFast.next.next!=null)
        {
            pSlow=pSlow.next;
            pFast=pFast.next.next;
        }
        ListNode mid=pSlow.next;
        pSlow.next=null;
        
        ListNode half1=sortList(head);
        ListNode half2=sortList(mid);
        //             
        ListNode sorted=mergeTwoLists(half1,half2);
        return sorted;
        
    }

クイックポインタの使い方は、この記事を参考にしてください.https://blog.csdn.net/To_be_to_thought/article/details/83958314
コード全体のパフォーマンスは、次のように優れています.

class Solution {
    public ListNode sortList(ListNode head) {
        
        if(head==null || head.next==null)
            return head;
        ListNode pFast=head,pSlow=head;
        while(pFast.next!=null && pFast.next.next!=null)
        {
            pSlow=pSlow.next;
            pFast=pFast.next.next;
        }
        ListNode mid=pSlow.next;
        pSlow.next=null;
        
        ListNode half1=sortList(head);
        ListNode half2=sortList(mid);
        
        ListNode sorted=mergeTwoLists(half1,half2);
        return sorted;
        
    }
    
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode head=null;
        if(l1.val

厳密には,再帰的空間複雑度はO(logn)であるが,LeetCodeでは暗黙的再帰的空間オーバーヘッドを計算しないことは,再帰的という簡潔で味わい深い方法で問題を解くことを奨励するが,実際の開発では避けなければならない.