leetcode真题-排序

一秉

一、题目描述
在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
Sort a linked list in O(n log n) time using constant space complexity.
示例1
输入
{3,2,4}
输出
{2,3,4}
二、代码实现（Java）
public class Solution {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode mid = findMid(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        return merge(left,right);
    }
     
    ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
     
    ListNode merge(ListNode l1, ListNode l2) {
        if (l1== null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}