[数据结构与算法]?java - 148. 排序链表? - 思路来源于归并排序

一、题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入：head = [4,2,1,3]
输出：[1,2,3,4]

二、思路(参考题解)

* 1 首先递归的把链表拆解，直至拆到单个节点
* 2 拆解后的一下一步就是归并，归并方法中的操作就是将2个有序子链表合并为一个新的升序链表返回
* 3 递归结束就已经完成了拆解+归并

三、代码

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;  // 拆分成单个节点或者空节点会把单节点本身返回
        ListNode scdHead = splitList(head); // 先分治：均分为2个子链表
        head = sortList(head); // 递归的排序子链表并返回，最底层是一个个的节点
        scdHead = sortList(scdHead);
        return mergeList(head, scdHead);  //返回上一层的已经是排好序的
    }

    public ListNode splitList(ListNode head) {
        /**
         * 传入一个父链表，将其拆分为2个子链表，返回第2个子链表头节点
         */
        ListNode tempHead = new ListNode(-1, head);
        ListNode fastPoint = tempHead;
        ListNode slowPoint = tempHead;
        while (fastPoint != null && fastPoint.next != null) { //快慢指针，实现找中点
            slowPoint = slowPoint.next;
            fastPoint = fastPoint.next.next;
        }
        ListNode resultNode = slowPoint.next;
        slowPoint.next = null;
        return resultNode;

    }

    public ListNode mergeList(ListNode fstList, ListNode scdList) {
        /**
         * 归并排序核心代码：
         * 传入2个升序的子链表，合并为新的升序父链表并返回
         */
        ListNode mergeNode = new ListNode(-1);
        ListNode node = mergeNode;
        ListNode node1 = fstList;
        ListNode node2 = scdList;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val){
                node.next = node1;
                node1 = node1.next;
            }else {
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }
        if (node1 != null) node.next = node1;
        else if (node2 != null) node.next = node2;
        return mergeNode.next;
    }

}