题解 | #单链表的排序#

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null)
            return head;
        // 使用快慢指针寻找链表的中点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 中间节点的下一个元素，用于右边元素递归的开始节点
        ListNode tmp = slow.next;
        // slow下个节点置空
        slow.next = null;
        // 递归左右两边进行排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);

        // 能来到这个地方，说明递归分割完了，需要进行归并操作
        // 创建新的链表用于合并之后的链表
        ListNode h = new ListNode(0); // 用于临时节点指针
        ListNode res = h;

        // 合并 left right两个链表
        while (left != null && right != null) {
            // left  right链表循环对比
            if (left.val < right.val) {
                // 左边节点小于右边节点值，直接拿新链表指向左边的节点，同时左节点重新复制左节点下一个节点
                h.next = left;
                left = left.next;
            } else {
                // 左边节点大于或等于右边节点值，直接拿新链表指向右边的节点，同时右边节点重新复制右节点下一个节点
                h.next = right;
                right = right.next;
            }
            // 头结点重置到下一个节点，进行下一轮的笔记拼接
            h = h.next;
        }
        
        // 最后添加未对比的链表部分判断左链表是否为空，直接拼接到头结点的下一个节点上
        h.next = left != null ? left : right;
        return res.next;
    }
}

解题思想：快慢指针确定中间值，递归分割链表为子序列，然后进行归并排序，最后赋值无需排序的剩余节点。