148. 排序链表

力扣题目链接 (opens new window)

题目描述

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

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内
• -10^5 <= Node.val <= 10^5

进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路

链表排序，首先想到的可能是把链表转成数组，排序后再转回链表。但这样空间复杂度是 O(n)，不符合题目进阶要求。

要在 O(n log n) 时间复杂度下排序，常见的算法有快速排序、归并排序、堆排序。

对于链表来说，归并排序是最合适的。

为什么？

• 快速排序需要随机访问元素做 pivot，链表不支持
• 堆排序需要数组结构
• 归并排序只需要顺序访问和合并操作，非常适合链表

归并排序思路

归并排序是典型的分治算法：

1. 分：找到链表中点，将链表分成两半
2. 治：递归排序左右两半
3. 合：合并两个有序链表

关键点一：如何找链表中点？

用快慢指针。快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针正好在中点。

关键点二：如何切断链表？

找到中点后，要把链表从中点切断，变成两个独立的链表。需要记录中点的前一个节点，将它的 next 置为 nullptr。

关键点三：如何合并两个有序链表？

这个在代码随想录 21.合并两个有序链表 中详细讲过了，用双指针逐个比较即可。

模拟过程

以示例 1 为例：[4,2,1,3]

第一次分割：找到中点 2 和 1 之间，分成 [4,2] 和 [1,3]

继续分割 [4,2]：分成 [4] 和 [2]

继续分割 [1,3]：分成 [1] 和 [3]

合并 [4] 和 [2]：得到 [2,4]

合并 [1] 和 [3]：得到 [1,3]

最后合并 [2,4] 和 [1,3]：得到 [1,2,3,4]

解题代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 递归终止条件：空链表或单节点链表已经有序
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // 快慢指针找中点
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = nullptr; // 记录慢指针的前一个节点，用于切断链表
        
        while (fast != nullptr && fast->next != nullptr) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        pre->next = nullptr; // 从中点切断链表
        
        // 递归排序左右两半
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        
        // 合并两个有序链表
        return merge(left, right);
    }
    
private:
    // 合并两个有序链表
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* cur = dummyHead;
        
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        
        // 连接剩余节点
        cur->next = (l1 != nullptr) ? l1 : l2;
        
        return dummyHead->next;
    }
};

复杂度分析

• 时间复杂度：O(n log n)，归并排序的标准复杂度
• 空间复杂度：O(log n)，递归调用栈的深度

其他语言

Python3

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件
        if not head or not head.next:
            return head
        
        # 快慢指针找中点
        slow, fast = head, head
        pre = None
        
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        pre.next = None  # 切断链表
        
        # 递归排序
        left = self.sortList(head)
        right = self.sortList(slow)
        
        # 合并
        return self.merge(left, right)
    
    def merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        
        cur.next = l1 if l1 else l2
        return dummy.next

Java

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 快慢指针找中点
        ListNode slow = head, fast = head;
        ListNode pre = null;
        
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        pre.next = null; // 切断链表
        
        // 递归排序
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        
        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;
        }
        
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

Go

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    // 快慢指针找中点
    slow, fast := head, head
    var pre *ListNode
    
    for fast != nil && fast.Next != nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    pre.Next = nil // 切断链表
    
    // 递归排序
    left := sortList(head)
    right := sortList(slow)
    
    return merge(left, right)
}

func merge(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }
    
    return dummy.Next
}

JS

var sortList = function(head) {
    if (!head || !head.next) {
        return head;
    }
    
    // 快慢指针找中点
    let slow = head, fast = head;
    let pre = null;
    
    while (fast && fast.next) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    pre.next = null; // 切断链表
    
    // 递归排序
    const left = sortList(head);
    const right = sortList(slow);
    
    return merge(left, right);
};

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let cur = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    
    cur.next = l1 || l2;
    return dummy.next;
}

与代码随想录联系

这道题综合了多个链表基本操作：

1. 快慢指针找中点 — 这个技巧在 141.环形链表 和 142.环形链表 II 中详细讲过
2. 合并两个有序链表 — 在 21.合并两个有序链表 中是独立题目
3. 分治递归思想 — 在代码随想录回溯章节有详细讲解

建议录友们先把这些基础题目理解透彻，再来做本题会轻松很多。

归并排序是为数不多适合链表的 O(n log n) 排序算法，面试中如果考察链表排序，基本就是这个思路。