Sort List ——LeetCode

Sort a linked list in O(n log n) time using constant space complexity.
 
チェーンテーブルのソートは、時間複雑度O(nlgn)を要求し、私が書いた集計ソートです.

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode sortList(ListNode head) {

        if(head==null){

            return head;

        }

        ListNode  tail = head;

        while(tail.next!=null){

            tail=tail.next;

        }

        return mergeList(head,tail);

    }

    

    ListNode mergeList(ListNode head,ListNode tail){

        if(head==tail){

            return head;

        }

        ListNode mid = getMid(head,tail);

        ListNode postList = mergeList(mid.next,tail);

        mid.next=null;

        ListNode preList = mergeList(head,mid);

        return merge(preList,postList);

    }

    

    ListNode getMid(ListNode head,ListNode tail){

        if(head==tail){

            return head;

        }

        ListNode fast = head,slow = head;

        while(fast.next!=null&&fast.next.next!=null&&fast.next!=tail){

            fast=fast.next.next;

            slow=slow.next;

        }

        return slow;

    }

    ListNode merge(ListNode l1,ListNode l2){

        if(l1==null||l2==null){

            return l1==null?l2:l1;

        }

        ListNode ptr = new ListNode(0);

        ListNode head = ptr;

        while(l1!=null&&l2!=null){

            if(l1.val<=l2.val){

                ptr.next = l1;

                l1=l1.next;

            }else{

                ptr.next = l2;

                l2=l2.next;

            }

            ptr=ptr.next;

        }

        ptr.next=l1==null?l2:l1;

        return head.next;

    }

}