148. 排序链表

// 排序链表 - 归并排序算法
// 时间复杂度：O(n log n)
// 空间复杂度：O(log n)

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    // 主函数：对链表进行排序
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 辅助函数：对从head到tail（不包含tail）的链表进行排序
    public ListNode sortList(ListNode head, ListNode tail) {
        // 边界情况：如果链表为空，直接返回
        if (head == null) {
            return head;
        }
        // 边界情况：如果链表只有一个节点，将其next设为null并返回
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 使用快慢指针找到链表的中点
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        // 中点即为slow
        ListNode mid = slow;
        // 递归排序左半部分
        ListNode list1 = sortList(head, mid);
        // 递归排序右半部分
        ListNode list2 = sortList(mid, tail);
        // 合并两个已排序的链表
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 合并两个已排序的链表
    public ListNode merge(ListNode head1, ListNode head2) {
        // 创建虚拟头节点，方便处理
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        // 比较两个链表的节点，将较小的节点添加到结果链表中
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        // 处理剩余的节点
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        // 返回合并后的链表头节点（跳过虚拟头节点）
        return dummyHead.next;
    }
}

// 示例用法
public class Main {
    public static void main(String[] args) {
        // 创建一个无序链表：4->2->1->3
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        
        System.out.println("原链表：");
        printList(head);
        
        // 排序链表
        Solution solution = new Solution();
        ListNode sortedHead = solution.sortList(head);
        
        System.out.println("排序后：");
        printList(sortedHead);
    }
    
    // 辅助函数：打印链表
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}