Java 利用递归实现链表的归并排序

Java 利用递归实现链表的归并排序

链表归并排序的思想

链表归并排序的思想与普通的排序算法类似，通过将待排数据不断分割直到只有一个节点，再利用 merge() 函数将它们合并起来，直到整个链表有序。相对于数组，链表的归并排序是一种稳定的排序，并且能够在O(n log n)的时间复杂度内完成排序。

Java 代码实现

以下是使用递归实现链表归并排序的 Java 代码示例：

public ListNode sortList(ListNode head) {
    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 right = sortList(slow.next);
    slow.next = null; 
    ListNode left = sortList(head);
    return merge(left, right);
}

private ListNode merge(ListNode l, ListNode r) {
    ListNode dummyHead = new ListNode(0);
    ListNode tail = dummyHead;
    while (l != null && r != null) {
        if (l.val < r.val) {
            tail.next = l;
            l = l.next;
        } else {
            tail.next = r;
            r = r.next;
        }
        tail = tail.next;
    }
    tail.next = l != null ? l : r;
    return dummyHead.next;
}

代码说明

该实现中，sortList() 函数采用快慢指针的方式将链表平分成左右两部分，接着递归调用 sortList() 函数对左右两部分进行分别排序，最后调用 merge() 函数将左右两部分有序地合并成一个链表。merge() 函数中，我们利用 dummyHead 和 tail 来生成一个新的链表。

代码使用示例

以下是一个简单的使用示例：

ListNode head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);
ListNode sortedList = sortList(head);
System.out.println(sortedList.val); // output: 1
System.out.println(sortedList.next.val); // output: 2
System.out.println(sortedList.next.next.val); // output: 3
System.out.println(sortedList.next.next.next.val); // output: 4

上述示例中，我们通过创建一个未排序的链表，并调用 sortList() 函数对其进行排序，最后输出排序后的链表节点的值。