148 排序链表

一、题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

二、题解

思路：归并排序 / 快慢指针 / 链表合并。

1. 核心思路

链表不适合使用数组中的快速排序，因为链表无法通过下标快速访问元素。

对于链表排序，更适合使用 归并排序。

归并排序的核心思想是：

  1. 将链表从中间拆成两部分。
  2. 分别对左右两部分链表进行排序。
  3. 将两个已经排好序的链表合并成一个有序链表。

由于每一层合并都需要遍历所有节点，而链表每次都会被拆成两半，所以时间复杂度是 O(nlog⁡n)O(n \log n)。

2. 具体步骤

  1. 如果链表为空，或者只有一个节点，说明已经有序，直接返回。
  2. 使用快慢指针找到链表的中点。
  3. 从中点位置断开链表，将链表分成左右两部分。
  4. 递归地排序左半部分链表。
  5. 递归地排序右半部分链表。
  6. 合并两个已经排好序的链表。
  7. 返回合并后的链表头节点。

3. 关键逻辑

这里最重要的逻辑有两个：

  • 如何找到链表中点。
  • 如何合并两个有序链表。

找中点时，使用快慢指针：

ListNode slow = head;
ListNode fast = head.next;

slow 每次走一步，fast 每次走两步。

当 fast 走到链表末尾时，slow 就停在链表中间偏左的位置。

然后断开链表：

ListNode rightHead = slow.next;
slow.next = null;

这样原链表就被拆成了两个链表：

head      -> 左半部分链表
rightHead -> 右半部分链表

合并两个有序链表时，每次比较两个链表当前节点的值，将较小的节点接到结果链表后面。

三、代码

/**
 * Definition for singly-linked list.
 * public 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) {
        // 1. 处理特殊情况
        // 如果链表为空，或者只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 2. 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 3. 从中点断开链表
        ListNode rightHead = slow.next;
        slow.next = null;

        // 4. 分别排序左右两部分链表
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 5. 合并两个有序链表
        return merge(left, right);
    }

    // 合并两个升序链表
    private ListNode merge(ListNode l1, ListNode l2) {
        // 虚拟头节点，方便处理链表头部
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        // 两个链表都不为空时，比较节点值
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        // 如果其中一个链表还有剩余节点，直接接到结果链表后面
        if (l1 != null) {
            cur.next = l1;
        }

        if (l2 != null) {
            cur.next = l2;
        }

        return dummy.next;
    }
}

四、复杂度分析

时间复杂度：O(nlog⁡n)O(n \log n)

说明：归并排序会不断将链表拆成两半，一共会拆分 log⁡n\log n 层。每一层合并时，都需要遍历所有节点，所以总时间复杂度是 O(nlog⁡n)O(n \log n)。

空间复杂度：O(log⁡n)O(\log n)

说明：递归归并排序会产生递归调用栈，递归深度是 log⁡n\log n，所以空间复杂度是 O(log⁡n)O(\log n)。

评论