ARTS-2-アルゴリズムの練習-チェーンベースの規格と並べ替え

概要:
左耳耗子コラム「左耳聴風」 ユーザは毎週ARTSを完成します。
1.Algorithm：毎週少なくとも1つのleetcodeのアルゴリズムの問題をします。
2.Review：少なくとも一つの英語技術記事を読み、評論する
3.Tip：少なくとも一つの技術技術を学ぶ
4.Share：観点と思考のある技術文章を共有する
 
Algorithm
テーマの概要:
Sort a linked list in O(n ロゴ n)time using constant space coplexity.
 
考え方の分析:
まずキーワードの空間複雑度がO（n logn）の順序付けアルゴリズムを見て、すぐに積み上げ順序と早い並びを考えました。しかし、タイトルはチェーンに基づいて並べ替えを実現しますので、この時は積み上げ順序のみを使ってこの問題を解決することができます。
コード:

package   .  ;

/**
 * Sort a linked list in O(n log n) time using constant space complexity.
 * 

 *                       ，    
 *            
 *
 * @author idea
 * @data 2019/4/11
 */

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class MergeSortLinkedTest {

    /**
     *   
     *
     * @param head
     * @return
     */
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode middle = head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            middle = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //    
        middle.next = null;
        ListNode l1 = sortList(head);
        //slow          
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }


    /**
     *            
     *
     * @param firstNode
     * @param nextNode
     * @return
     */
    private static ListNode merge(ListNode firstNode, ListNode nextNode) {
        ListNode resultList = new ListNode(0);
        ListNode cur = resultList;
        while (firstNode != null && nextNode != null) {
            if (firstNode.val <= nextNode.val) {
                cur.next = firstNode;
                firstNode = firstNode.next;
            } else {
                cur.next = nextNode;
                nextNode = nextNode.next;
            }
            cur = cur.next;
        }
        if (firstNode != null) {
            cur.next = firstNode;
        }
        if (nextNode != null) {
            cur.next = nextNode;
        }
        //head is not reight node
        return resultList.next;
    }


    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(22);
        ListNode node5 = new ListNode(6);
        ListNode node6 = new ListNode(16);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        sortList(node);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

}