题解 | 链表排序

import java.util.*;

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

public class Solution {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }

        // 获取链表长度
        int length = getLength(head);

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 从大小为1开始，每次翻倍
        for (int size = 1; size < length; size *= 2) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;

            while (curr != null) {
                // 获取第一个子链表
                ListNode left = curr;
                ListNode right = split(left, size);
                curr = split(right, size);

                // 合并两个有序链表
                ListNode merged = merge(left, right);
                prev.next = merged;

                // 移动prev到合并后链表的末尾
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }

        return dummy.next;
    }

    // 获取链表长度
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // 分割链表，返回后半部分的头节点
    private ListNode split(ListNode head, int size) {
        if (head == null) return null;

        // 移动到第size个节点
        for (int i = 1; i < size && head.next != null; i++) {
            head = head.next;
        }

        ListNode right = head.next;
        head.next = null; // 断开连接
        return right;
    }

    // 合并两个有序链表
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 连接剩余部分
        if (l1 != null) {
            curr.next = l1;
        } else {
            curr.next = l2;
        }

        return dummy.next;
    }

}