题解 | #单链表的排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        //step1：基本判空处理
        if(head == null || head.next == null){
            return head;
        }
        //step2:使用快慢指针，查询当前本次归并处理的中点
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null){ //保证快指针不会异常
            slow = slow.next;
            fast = fast.next.next;
        }
        //step3:找到本轮中点节点,进行两链表的拆分
        ListNode temp = slow.next;
        slow.next = null;  //断开链表
        //step4：归并继续拆分、合并
        return mergeList(sortInList(head),sortInList(temp));
    }


    public ListNode mergeList(ListNode head1,ListNode head2){
        //基本判空
        if(head1 == null){return head2;}
        if(head2 == null){return head1;}

        //构造双指针
        ListNode head1Cursor = head1;
        ListNode head2Cursor = head2;

        //构造新的头节点，移动双指针
        ListNode newHead = new ListNode(0);
        ListNode newCursor = newHead; 
        while(head1Cursor!=null && head2Cursor!=null){
            if(head1Cursor.val<head2Cursor.val){
                newCursor.next = head1Cursor;
                head1Cursor = head1Cursor.next;
            }else {
                newCursor.next = head2Cursor;
                head2Cursor = head2Cursor.next;
            }
            //移动newCursor
            newCursor = newCursor.next;
        }
        //head1Cursor和head2Cursor存在提前终止的情况，需连接其后半部分
        newCursor.next = head1Cursor == null ? head2Cursor : head1Cursor;

        return newHead.next;
    }
}