题解 | #NC70 单链表的排序#

和力扣 剑指 Offer II 077. 链表排序 相同

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 slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 将链表分成两半并返回后半部分链表的头节点
        ListNode newList = slow.next;
        slow.next = null;

        // 对前后两个链表不断进行递归，直到最后只有两个节点，然后逐层返回
        ListNode left = sortInList(head);
        ListNode right = sortInList(newList);

        // 将两个链表排序，并合并为一个链表
        return mergeTwo(left, right);
        
    }
    
    public ListNode mergeTwo(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) 
            return node1 == null ? node2 : node1;
        ListNode head = new ListNode(0);
        ListNode tmp = head, tmp1 = node1, tmp2 = node2;
        
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val <= tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        
        tmp.next = tmp1 == null? tmp2 : tmp1;
        
        return head.next;
    }
}