Swift 实现链表重新排列：L0 → Ln → L1 → Ln-1

前言

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

143. 重排链表

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

难度水平：中等

摘要

链表的重新排列是链表操作的进阶问题。本篇文章将讲解如何在 Swift 中实现 链表的重新排列，从而使其节点顺序变为 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …，并提供完整代码、测试案例及时间空间复杂度分析。

描述

给定一个单链表 L **的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

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

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

题解答案

重新排列链表可以分为以下 3 个步骤：

1. 找到链表的中点：
   • 使用快慢指针法找到链表的中间节点。
2. 反转后半部分链表：
   • 从中间节点开始，反转链表的后半部分。
3. 合并两部分链表：
   • 交替合并前半部分和反转后的后半部分。

以下是 Swift 的完整代码实现：

题解代码

// 定义链表节点
class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reorderList(_ head: ListNode?) {
    guard let head = head else { return }
    
    // Step 1: 找到链表中点
    var slow: ListNode? = head
    var fast: ListNode? = head
    
    while fast?.next != nil && fast?.next?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }
    
    // Step 2: 反转链表后半部分
    var prev: ListNode? = nil
    var current = slow?.next
    slow?.next = nil // 切断前后链表
    
    while current != nil {
        let nextTemp = current?.next
        current?.next = prev
        prev = current
        current = nextTemp
    }
    
    // Step 3: 合并两部分链表
    var first: ListNode? = head
    var second: ListNode? = prev
    
    while second != nil {
        let temp1 = first?.next
        let temp2 = second?.next
        
        first?.next = second
        second?.next = temp1
        
        first = temp1
        second = temp2
    }
}

题解代码分析

Step 1: 找链表中点

• 使用快慢指针法：
  • 慢指针 slow 每次前进一步。
  • 快指针 fast 每次前进两步。
  • 当 fast 或 fast.next 为 nil 时，slow 停在中点。

Step 2: 反转后半部分链表

• 从中间节点开始，逐步反转链表后半部分的指针。
• prev 指向已反转部分的头部，current 指向正在处理的节点。

Step 3: 合并两部分链表

• 使用两个指针 first 和 second 分别遍历前半部分和反转后的后半部分。
• 按照交替顺序重新连接节点。

示例测试及结果

以下是测试代码：

// 创建链表节点
func createLinkedList(_ values: [Int]) -> ListNode? {
    guard !values.isEmpty else { return nil }
    let head = ListNode(values[0])
    var current = head
    
    for val in values.dropFirst() {
        current.next = ListNode(val)
        current = current.next!
    }
    return head
}

// 打印链表
func printLinkedList(_ head: ListNode?) {
    var current = head
    while current != nil {
        print(current!.val, terminator: " ")
        current = current?.next
    }
    print()
}

// 示例 1
let head1 = createLinkedList([1, 2, 3, 4])
reorderList(head1)
printLinkedList(head1) // 输出: 1 4 2 3

// 示例 2
let head2 = createLinkedList([1, 2, 3, 4, 5])
reorderList(head2)
printLinkedList(head2) // 输出: 1 5 2 4 3

测试结果:

1 4 2 3 
1 5 2 4 3

时间复杂度

1. 寻找中点： 快慢指针遍历链表一次，复杂度为 O(n)。
2. 反转后半部分链表： 遍历后半部分链表一次，复杂度为 O(n/2)。
3. 合并链表： 遍历整个链表一次，复杂度为 O(n)。

总时间复杂度： O(n)。

空间复杂度

• 使用常量级指针变量 (slow, fast, prev, current 等)，额外空间复杂度为 O(1)。

总结

本题通过三步解决链表重新排列问题，重点在于快慢指针、链表反转及合并操作的结合使用。

关键点总结：

1. 快慢指针找到链表中点是链表问题的通用技巧。
2. 反转链表是基础操作，但需要切断前后部分以防止循环。
3. 合并链表时注意节点指向的正确性。

本篇文章提供的解决方案既高效又优雅，适合链表相关问题的学习与实战。如果你有其他更优的方法，欢迎交流！

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。