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 个步骤：

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

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

题解代码

// 定义链表节点
class ListNode {var val: Intvar next: ListNode?init(_ val: Int) {self.val = valself.next = nil}
}func reorderList(_ head: ListNode?) {guard let head = head else { return }// Step 1: 找到链表中点var slow: ListNode? = headvar fast: ListNode? = headwhile fast?.next != nil && fast?.next?.next != nil {slow = slow?.nextfast = fast?.next?.next}// Step 2: 反转链表后半部分var prev: ListNode? = nilvar current = slow?.nextslow?.next = nil // 切断前后链表while current != nil {let nextTemp = current?.nextcurrent?.next = prevprev = currentcurrent = nextTemp}// Step 3: 合并两部分链表var first: ListNode? = headvar second: ListNode? = prevwhile second != nil {let temp1 = first?.nextlet temp2 = second?.nextfirst?.next = secondsecond?.next = temp1first = temp1second = 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 = headfor val in values.dropFirst() {current.next = ListNode(val)current = current.next!}return head
}// 打印链表
func printLinkedList(_ head: ListNode?) {var current = headwhile 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