Java无序链表排序

Java中对无序链表进行排序的一种常见方法是使用归并排序（Merge Sort）。对于链表这种数据结构，直接遍历和比较元素比较复杂，因为我们需要考虑节点间的迭代。以下是归并排序链表的基本步骤：

1. **递归分割**：将链表不断二分，直到每个子链表只有一个元素。
2. **合并**：将相邻的两个已排序链表合并成一个更大的有序链表，通过一个新的头节点连接它们，同时保持顺序。
3. **合并过程**：在合并过程中，创建一个临时节点作为新链表的头，然后依次比较两个链表当前节点的值，将较小的节点添加到临时节点，并移动指针。当一个链表遍历完，将另一个链表剩余部分添加到结果链表。

以下是Java中的示例代码片段：

public class ListNode {
    int val;
    ListNode next;
    // constructor, getters and setters...
}

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    // Step 1: Divide the list into two halves
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;

    // Step 2: Recursively sort each half
    ListNode left = sortList(head);
    ListNode right = sortList(mid);

    // Step 3: Merge the sorted halves
    return merge(left, right);
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = l1 == null ? l2 : l1;
    return dummy.next;
}