链表排序

时间复杂度为: nlog(n)
归并排序的时间复杂度是 nlog(n)
解题思路:
1.找到链表的中间节点
2.注意：要保证从head到mid之后，就不能继续排序
所以要将mid.next备份为midNext，并将mid.next置为null
3.归并排序链表

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

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 = getMidNode(head);
        // 下面的环节重要
        ListNode midNext = mid.next;
        mid.next = null;
        // 上面的环节重要
        ListNode leftPart = sortList(head);
        ListNode rightPart = sortList(midNext);
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(leftPart != null && rightPart != null){
            if(leftPart.val <= rightPart.val){
                cur.next = new ListNode(leftPart.val);
                leftPart = leftPart.next;
            }else{
                cur.next = new ListNode(rightPart.val);
                rightPart = rightPart.next;
            }
            cur = cur.next;
        }
        while(leftPart != null){
            cur.next = new ListNode(leftPart.val);
            cur = cur.next;
            leftPart = leftPart.next;
        }
        while(rightPart != null){
            cur.next = new ListNode(rightPart.val);
            cur = cur.next;
            rightPart = rightPart.next;
        }
        return dummy.next;
    }

    public ListNode getMidNode(ListNode head){
        if(head == null || head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}