题解 | #链表排序#

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 slow = head, fast = head.next;

        while (fast != null && fast.next != null) {  
            //使用快慢指针寻找中间 结点
            //结束时，slow正好在中间
            slow = slow.next;

            fast = fast.next;
            if (fast.next != null)
                fast = fast.next;
        }

        ListNode ptr1 = slow.next;
        slow.next = null;

        ListNode tmp1 = sortList(head);
        ListNode tmp2 = sortList(ptr1);
        return merge(tmp1, tmp2);
    }


    public ListNode merge(ListNode start1, ListNode start2) {
        ListNode header = new ListNode(-1);
        ListNode pre = header;

        ListNode ptr1 = start1, ptr2 = start2;
        while (ptr1 != null && ptr2 != null) {
            if (ptr1.val <= ptr2.val) {
                //若小于，则 ptr1 往下移动
                pre.next = ptr1;
                pre = ptr1;
                ptr1 = ptr1.next;
            } else {
                //若大于，则 ptr1 往下移动
                pre.next = ptr2;
                pre = ptr2;
                ptr2 = ptr2.next;
            }
        }
        while (ptr1 != null) {
            pre.next = ptr1;
            pre = ptr1;
            ptr1 = ptr1.next;
        }

        while (ptr2 != null) {
            pre.next = ptr2;
            pre = ptr2;
            ptr2 = ptr2.next;
        }


        return header.next;

    }
}