题解 | #单链表的排序#

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) {
        // write code here
        /** int n = 0;
        ListNode tmp = head;
        while(tmp != null){
            n++;
            tmp = tmp.next;
        }
        return mergeSort(head, n);
        */
        return mergeSort(head);
    }

    /** ListNode mergeSort(ListNode leftNode, int n){
         ListNode tmp = leftNode;
        //如果n为1，说明已经划分到最小
        if(n == 1)   return leftNode;
        int mid = n/2;
        ListNode midNode = leftNode;
        //遍历到B链表的头节点的前一个节点
        for(int i=0; i<mid-1; i++){
            midNode = midNode.next;
        }
        //截断链表
        tmp = midNode;
        midNode = midNode.next;
        tmp.next = null;
        
        leftNode = mergeSort(leftNode, n/2);
        midNode = mergeSort(midNode, n-n/2);
        //合并
        return merge(leftNode, midNode);
    }*/

    ListNode mergeSort(ListNode leftNode){
         ListNode tmp = leftNode;
        //说明已经划分到最小
        if(leftNode.next == null)   return leftNode;
        ListNode fast=leftNode,slow=leftNode;
        ListNode midNode = leftNode;
        //midNode遍历到B链表的头节点的前一个节点
        while(fast!=null&&fast.next!=null){
            midNode = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //截断链表
        tmp = midNode;
        midNode = midNode.next;
        tmp.next = null;
        
        leftNode = mergeSort(leftNode);
        midNode = mergeSort(midNode);
        //合并
        return merge(leftNode, midNode);
    }
    //**太繁琐了 */
    ListNode merge(ListNode leftNode, ListNode midNode){
        //需要一个空头节点来处理合并，否则无法返回第一个节点
        ListNode dummy = new ListNode(0);
        dummy.next = leftNode;
        ListNode tmp = dummy.next;
        //处理比B链中比A链第一个节点小的归并
        while(midNode!=null){
            if(midNode.val <= leftNode.val){
                dummy.next = midNode;
                midNode = midNode.next;
                dummy.next.next = leftNode;
                leftNode = dummy.next;
            }
            else break;
        }
        tmp = dummy.next;
        while(midNode!=null){
            if(midNode.val>=tmp.val ){
                if(tmp.next == null) {
                    tmp.next = midNode;
                    break;
                }
                if(tmp.next.val <= midNode.val) {
                    tmp = tmp.next;
                    continue;
                }
                if(tmp.next.val > midNode.val){
                    ListNode next = midNode.next;
                    midNode.next = tmp.next;
                    tmp.next = midNode;
                    midNode = next;
                }
            }
        }
        return dummy.next;
    }

    //别人写的
    public ListNode merge1(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (left != null && right != null) {
        if (left.val < right.val) {
            cur.next = left;
            left = left.next;
        } else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next;
    }
    if (left != null) {
        cur.next = left;
    }
    if (right != null) {
        cur.next = right;
    }
    return dummy.next;
}

    
}

归并排序，时间复杂度为O（nlogn）

分为两个步，一步是分，一步是合。

需要注意的有，mergeSort函数中，从中间切分链表，中间节点可以通过快慢指针寻找，也可以计算出链表长度，划分的时候多传一个链表长度参数。

//midNode遍历到B链表的头节点的前一个节点
        while(fast!=null&&fast.next!=null){
            midNode = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

遍历以后slow指向的就是后一个链表的头节点，而midNode指向的是前一半链表的尾节点。

然后就是merge函数，这个我写的太复杂了。参考了别人的写法merge1，比较清晰。思路是直接用一个伪头节点来依次连接两个链表头节点中，小的那个节点。这里的写法很简洁，不需要一个个节点连到dummy后面，直接将头节点小的链表连到dummy后面，然后用cur的指向已排序好的链表尾部。