Swift实现高效链表排序：一步步解读

在这里插入图片描述

文章目录

- 前言
- 摘要
- 问题描述
- 题解
- - 解题思路
  - Swift 实现代码
  - 代码分析
  - 示例测试与结果
- 时间复杂度
- 空间复杂度
- 总结
- 关于我们

前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

148. 排序链表

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

摘要

如何高效地对链表进行升序排序一直是算法中的经典问题之一。本文将深入解析如何使用Swift语言实现基于归并排序的链表排序算法，满足O(n log n)的时间复杂度和常数级空间复杂度的需求。同时，提供一段可运行的代码模块，帮助读者快速理解和实战。

问题描述

给定一个单链表的头结点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, 10^5]

进阶要求

在O(n log n)时间复杂度和常数级空间复杂度下完成链表排序。

题解

解题思路

归并排序是链表排序的理想选择，因其适合链表的顺序特性，并能够在O(n log n)时间复杂度内完成排序：

分割链表：递归地将链表从中间分为两个子链表，直到每个子链表只有一个节点。
合并有序链表：将两个已排序的链表按照升序合并成一个新的有序链表。

Swift 实现代码

class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func sortList(_ head: ListNode?) -> ListNode? {
    // 基本情况：空链表或只有一个节点
    guard let head = head, head.next != nil else {
        return head
    }

    // 使用快慢指针找到链表中点
    let mid = findMiddle(head)
    let rightHead = mid.next
    mid.next = nil

    // 递归对两部分排序
    let left = sortList(head)
    let right = sortList(rightHead)

    // 合并排序后的两部分
    return merge(left, right)
}

func findMiddle(_ head: ListNode) -> ListNode {
    var slow = head
    var fast = head

    while fast.next != nil, fast.next?.next != nil {
        slow = slow.next!
        fast = fast.next!.next!
    }

    return slow
}

func merge(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    var current = dummy
    var l1 = l1
    var l2 = l2

    while let node1 = l1, let node2 = l2 {
        if node1.val < node2.val {
            current.next = node1
            l1 = node1.next
        } else {
            current.next = node2
            l2 = node2.next
        }
        current = current.next!
    }

    current.next = l1 ?? l2
    return dummy.next
}

代码分析

查找链表中点
- 使用快慢指针找到链表的中间节点并将链表分成两部分。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
递归排序
- 不断分割链表直到只有一个节点时停止递归，然后逐步合并已排序的链表。
合并有序链表
- 使用双指针遍历两个已排序链表，按值大小将节点逐个合并。
- 时间复杂度：O(n)
- 空间复杂度：O(1)

示例测试与结果

测试代码

func printList(_ head: ListNode?) {
    var current = head
    var result: [Int] = []
    while let node = current {
        result.append(node.val)
        current = node.next
    }
    print(result)
}

// 创建示例链表：[4, 2, 1, 3]
let head = ListNode(4)
head.next = ListNode(2)
head.next?.next = ListNode(1)
head.next?.next?.next = ListNode(3)

// 调用排序函数
let sortedHead = sortList(head)

// 打印结果
printList(sortedHead) // 输出：[1, 2, 3, 4]