LeetCode 148 排序链表：归并排序实现O(nlogn)复杂度

题目描述

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

进阶：

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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)的时间复杂度，我们可以使用归并排序。主要步骤如下：

1. 使用快慢指针找到链表中点，将链表分为两半
2. 对两个子链表递归进行归并排序
3. 合并两个有序链表

关键点：

1. 使用快慢指针（快指针每次走两步，慢指针每次走一步）找到链表中点
2. 通过递归实现分治
3. 合并两个有序链表时使用哑节点简化操作

时间复杂度：O(n log n)，其中n是链表长度。 空间复杂度：O(log n)，递归调用的栈空间。

方法二：自底向上归并排序

为了实现O(1)的空间复杂度，我们可以使用自底向上的归并排序：

1. 首先求得链表长度
2. 将链表拆分成子链表进行合并，子链表的长度从1开始，每次翻倍
3. 重复步骤2直到子链表长度大于等于链表长度

关键点：

1. 使用循环而不是递归，避免栈空间
2. 每次合并前需要拆分链表
3. 使用哑节点简化合并操作

时间复杂度：O(n log n)，其中n是链表长度。 空间复杂度：O(1)，只使用常数额外空间。

图解思路

以示例1为例，演示自底向上归并排序的过程：

1. 初始状态，每组长度为1：

[4] [2] [1] [3]

2. 两两合并后，每组长度为2：

[2,4] [1,3]

3. 最终合并，得到排序后的链表：

[1,2,3,4]

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 计算链表长度
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 自底向上归并排序
        for (int size = 1; size < length; size *= 2) {
            ListNode curr = dummy.next;
            ListNode tail = dummy;
            
            while (curr != null) {
                ListNode left = curr;
                ListNode right = Cut(left, size);
                curr = Cut(right, size);
                
                tail.next = Merge(left, right);
                while (tail.next != null) {
                    tail = tail.next;
                }
            }
        }
        
        return dummy.next;
    }
    
    // 将链表切分，返回后半部分的头节点
    private ListNode Cut(ListNode head, int n) {
        if (head == null) return null;
        
        ListNode curr = head;
        while (--n > 0 && curr != null) {
            curr = curr.next;
        }
        
        if (curr == null) return null;
        
        ListNode next = curr.next;
        curr.next = null;
        return next;
    }
    
    // 合并两个有序链表
    private ListNode Merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = l1 ?? l2;
        return dummy.next;
    }
}

Python 实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
            
        # 计算链表长度
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
            
        dummy = ListNode(0)
        dummy.next = head
        
        # 自底向上归并排序
        size = 1
        while size < length:
            curr = dummy.next
            tail = dummy
            
            while curr:
                left = curr
                right = self.cut(left, size)
                curr = self.cut(right, size)
                
                tail.next = self.merge(left, right)
                while tail.next:
                    tail = tail.next
                    
            size *= 2
            
        return dummy.next
        
    def cut(self, head, n):
        if not head:
            return None
            
        curr = head
        while curr and n > 1:
            curr = curr.next
            n -= 1
            
        if not curr:
            return None
            
        next_head = curr.next
        curr.next = None
        return next_head
        
    def merge(self, l1, l2):
        dummy = ListNode(0)
        curr = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
            
        curr.next = l1 or l2
        return dummy.next

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        // 计算链表长度
        int length = 0;
        ListNode* node = head;
        while (node) {
            length++;
            node = node->next;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        // 自底向上归并排序
        for (int size = 1; size < length; size *= 2) {
            ListNode* curr = dummy->next;
            ListNode* tail = dummy;
            
            while (curr) {
                ListNode* left = curr;
                ListNode* right = cut(left, size);
                curr = cut(right, size);
                
                tail->next = merge(left, right);
                while (tail->next) {
                    tail = tail->next;
                }
            }
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
    
private:
    ListNode* cut(ListNode* head, int n) {
        if (!head) return nullptr;
        
        ListNode* curr = head;
        while (--n > 0 && curr) {
            curr = curr->next;
        }
        
        if (!curr) return nullptr;
        
        ListNode* next = curr->next;
        curr->next = nullptr;
        return next;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        
        curr->next = l1 ? l1 : l2;
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	128 ms	48.9 MB	实现简洁，性能适中
Python	468 ms	36.7 MB	代码最简洁
C++	96 ms	48.2 MB	性能最优

补充说明

代码亮点

1. 使用自底向上的归并排序实现O(1)空间复杂度
2. 通过哑节点简化链表操作
3. 封装了cut和merge函数，提高代码可读性和复用性

常见错误

1. 递归实现导致空间复杂度不符合要求
2. 链表切分时没有正确处理边界情况
3. 合并过程中指针更新顺序错误

相关题目

• 147. 对链表进行插入排序
• 21. 合并两个有序链表
• 23. 合并K个升序链表

讨论

有几个问题可以思考一下：

1. 归并排序递归和迭代两种方法，哪个更难理解？哪个更实用？
2. 为什么链表排序用归并排序，而不是快排？
3. 题目进阶要求O(1)空间，但递归会用栈空间，这算不算额外空间？

欢迎在评论区讨论。

---

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。