手把手带你学算法——排序链表（148）

欢迎来到本教程的一篇新文章，今天我们将学习如何解决LeetCode中的问题148——"排序链表"。这个问题要求我们对链表进行排序，要求时间复杂度为 O(n log n)。通过学习如何使用归并排序算法来解决这个问题，你将提高你的链表处理和算法设计能力。

问题描述

题目描述如下：

给定一个链表的头节点，将链表重新排列成升序排序的链表。要求在 O(n log n) 时间复杂度和常数空间复杂度下完成。

示例：

假设我们有一个链表 4 → 2 → 1 → 3，排序后变成 1 → 2 → 3 → 4。

解决思路

要解决这个问题，我们可以使用归并排序（Merge Sort）算法。具体的解决步骤如下：

1. 首先，找到链表的中点，将链表拆分成两个子链表。可以使用快慢指针法来找到中点。

2. 递归地对两个子链表进行排序。

3. 合并两个已排序的子链表，得到最终的有序链表。合并过程可以使用归并排序中的合并操作来完成。

4. 返回排序后的链表。

Python代码实现

下面是使用Python实现的解决方案代码：

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        # 找到链表中点
        mid = self.findMiddle(head)
        left = head
        right = mid.next
        mid.next = None
        
        # 递归排序两个子链表
        left_sorted = self.sortList(left)
        right_sorted = self.sortList(right)
        
        # 合并两个有序链表
        return self.merge(left_sorted, right_sorted)
    
    def findMiddle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def merge(self, left: ListNode, right: ListNode) -> ListNode:
        dummy = ListNode()
        current = dummy
        
        while left and right:
            if left.value < right.value:
                current.next = left
                left = left.next
            else:
                current.next = right
                right = right.next
            current = current.next
        
        if left:
            current.next = left
        if right:
            current.next = right
        
        return dummy.next

示例

现在让我们看一个示例，演示如何使用这个算法来对链表进行排序：

# 创建一个未排序的链表
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

# 排序链表
solution = Solution()
sorted_head = solution.sortList(head)

# 打印排序后的链表
current = sorted_head
while current:
    print(current.value, end=" → ")
    current = current.next

结论

通过这篇教程，我们学习了如何解决LeetCode问题148——"排序链表"，并提供了相应的Python代码示例。希望这个教程帮助你理解如何使用归并排序算法对链表进行排序，并在时间复杂度为 O(n log n) 和常数空间复杂度下完成。在接下来的教程中，我们将继续学习更多有关数据结构和算法的知识。感谢阅读！