【124期】字节一面面试官问：Java 如何实现链表中归并排序？

素文宅博客 Java精选 2022-08-09

收录于合集 #面试题系列专栏 349个

点击上方“Java精选”，选择“设为星标”

别问别人为什么，多问自己凭什么！

下方留言必回，有问必答！

每天 08:00 更新文章，每天进步一点点...

这是一道字节跳动实习生面试时的面试题，首选先说说什么是归并排序。

归并排序可以说是链表排序中最佳的选择，能够保证最好和最坏时间复杂度都是nlogn，而且在数组排序中广受开发人反感的空间复杂度在链表排序中也从O(n)降到了O(1)。

归并排序的一般分为四步：

1）将需要排序数组（链表）取中点并一分为二，拆分为两个链表：head和second两个子链表；

2）使用递归方式对左半部分子链表进行归并排序；

3）使用递归方式对右半部分子链表进行归并排序；

4）将两个半部分子链表进行合并（merge），得到结果。

首先用快慢指针（快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）的方法找到链表中间节点，然后使用递归对两个子链表排序，把两个排好序的子链表合并成一条有序的链表。

程序代码，为了方便输出查看结果，使用Gson包，不需要可以去除相关代码：

import com.google.gson.Gson;
 
class ListNode {
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class LinkedInsertSort {
 
    /**
     * @author 公众号：Java精选
     * @param args
     */
    public static void main(String[] args) {
        ListNode node = new ListNode(4);
        node.next = new ListNode(3);
        LinkedInsertSort lss = new LinkedInsertSort();
        System.out.println(new Gson().toJson(lss.mergeSort(node)));
    }
 
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null)
            return head;
 
        ListNode mid = getMid(head);// 获取链表中间节点
 
        // 把链表从之间拆分为两个链表：head和second两个子链表
        ListNode second = mid.next;
        mid.next = null;
 
        // 对两个子链表排序
        ListNode left = mergeSort(head);
        ListNode right = mergeSort(second);
 
        return merge(right, left);
    }
 
    // 两个有序链表的归并
    private ListNode merge(ListNode l1, ListNode l2) {
        // 辅助节点，排好序的节点将会链接到dummy后面
        ListNode dummy = new ListNode(0);
 
        ListNode tail = dummy;// tail指向最后一个排好序的节点
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next; // 移动tail指针
        }
 
        if (l1 != null)
            tail.next = l1;
        else
            tail.next = l2;
 
        return dummy.next;
 
    }
 
    // 返回链表之间节点
    private ListNode getMid(ListNode head) {
        if (head == null || head.next == null)
            return head;
 
        ListNode slow = head;
        ListNode faster = head.next;
        while (faster != null && faster.next != null) {
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }
}