Leetcode 148.排序链表（归并排序）

解题思路：由时间复杂度要求O(nlogn)，容易想到快速排序、堆排序、归并排序几种方法，其中适用于链表的是归并排序方法。归并排序分为自顶向下和自底向上两种实现方法，比起自顶向下方法，自底向上的方法省去了递归函数栈使用的空间，使空间复杂度降到了O(1)。
这里给出自自顶向下的归并排序实现。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//归并排序（自顶向下迭代）
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)    return head;

        //1.快慢指针遍历链表，找到链表中间结点
        ListNode slow = head, fast = head.next;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //2.slow指向的为head1的尾结点，fast指向的为head2的尾结点， head2 = slow.next
        ListNode head2 = slow.next;
        slow.next = null;   //使左右链表断开
        if(head.next!=null)     head = sortList(head);
        if(head2.next!=null)    head2 = sortList(head2);

        //3.对已排序的左右链表归并
        return merge(head, head2);
    }

    private ListNode merge(ListNode l1, ListNode l2){
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}