前言
有需要的同学可以订阅专栏：Swift数据结构和算法专题
代码地址：Swift数据结构和算法代码
正文
在本章中，我们将了解链表的五个常见场景。与大多数问题相比，这些问题相对容易，它们将有助于巩固我们对数据结构的了解。
打开启动项目开始。解决如下问题。
问题一：反转打印
创建一个以相反顺序打印链表节点的函数。例如：
1 -> 2 -> 3 -> nil
// should print out the following:
3
2
1
问题 2：寻找中间节点
创建一个查找链表中间节点的函数。例如：
1 -> 2 -> 3 -> 4 -> nil
// 中间是 3
1 -> 2 -> 3 -> nil
// 中间是 2
问题 3：反转链表
创建一个反转链表的函数。我们可以通过操作节点来实现这一点，以便它们在另一个方向上链接。例如：
// before
1 -> 2 -> 3 -> nil
// after
3 -> 2 -> 1 -> nil
问题 4：合并两个列表
创建一个函数，该函数采用两个排序的链表并将它们合并为一个排序的链表。我们的目标是返回一个新的链表，其中包含按排序顺序来自两个列表的节点。我们可以假设排序顺序是升序的。例如：
// list1
1 -> 4 -> 10 -> 11
// list2
-1 -> 2 -> 3 -> 6
// merged list
-1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 10 -> 11
问题 5：删除所有事件
创建一个函数，从链表中删除所有出现的特定元素。该实现类似于我们为链表实现的 remove(at:) 方法。例如：
// original list
1 -> 3 -> 3 -> 3 -> 4
// list after removing all occurrences of 3
1 -> 4
解决方案
问题1解决方案
解决此问题的一种直接方法是使用递归。由于递归允许我们构建调用堆栈，因此我们只需在调用堆栈展开时调用打印语句。我们的第一个任务是递归遍历到最后。将以下辅助函数添加到我们的Playground：
private func printInReverse<T>(_ node: Node<T>?) {
// 1
guard let node = node else { return }
// 2
printInReverse(node.next)
}
- 1.我们首先从基本情况开始：终止递归的条件。如果 node 为 nil，则表示我们已到达列表的末尾。
- 这是我们的递归调用，调用与下一个节点相同的函数。
打印
我们添加打印语句的位置将决定我们是否以相反的顺序打印列表。
将函数更新为以下内容：
private func printInReverse<T>(_ node: Node<T>?) {
guard let node = node else { return }
printInReverse(node.next)
print(node.value)
}
任何代码 只有在基本情况触发之后（即，在递归函数到达列表末尾之后）才调用递归调用之后。随着递归语句的展开，节点数据被打印出来。
最后，我们需要从原始 printInReverse 函数中调用辅助方法。将其更新为如下所示：
func printInReverse<T>(_ list: LinkedList<T>) {
printInReverse(list.head)
}
在 Playground页面的底部写下以下内容：
example(of: "printing in reverse") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Original list: \(list)")
print("Printing in reverse:")
printInReverse(list)
}
我们应该看到以下输出：
---Example of printing in reverse---
Original list: 1 -> 2 -> 3
Printing in reverse:
3
2
1
该算法的时间复杂度为 O(n)，因为我们必须遍历列表的每个节点。空间复杂度同样为 O(n)，因为我们隐式使用函数调用堆栈来处理每个元素。
问题 2 的解决方案
一种解决方案是让两个引用遍历列表的节点，其中一个的速度是另一个的两倍。一旦较快的参考到达终点，较慢的参考将在中间。将函数更新为以下内容：
func getMiddle<T>(_ list: LinkedList<T>) -> Node<T>? {
var slow = list.head
var fast = list.head
while let nextFast = fast?.next {
fast = nextFast.next
slow = slow?.next
}
return slow
}
在 while 声明中，将下一个节点绑定到 nextFast。如果有下一个节点，则快速更新到 nextFast 的下一个节点，有效地遍历列表两次。慢速指针只更新一次。这被称为跑步者的技术。
在 Playground页面底部写下以下内容：
example(of: "getting the middle node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print(list)
if let middleNode = getMiddle(list) {
print(middleNode)
}
}
你应该看到以下输出：
---Example of getting the middle node---
1 -> 2 -> 3
2 -> 3
该算法的时间复杂度为 O(n)，因为我们一次遍历了列表。
问题3的解决方案
要反转链表，我们必须访问每个节点并更新下一个引用以指向另一个方向。这可能是一项棘手的任务，因为我们需要管理对多个节点的多个引用。简单的方法 我们可以使用 push方法和一个新的临时列表轻松地反转列表。更新 Playground中的代码：
extension LinkedList {
mutating func reverse() {
// 1
for value in self {
tmpList.push(value)
}
// 2
head = tmpList.head
}
}
- 首先将列表中的当前值推送到新的 tmpList。这将以相反的顺序创建一个列表。
- 我们将列表的头部指向反向节点。
O(n) 时间复杂度。
虽然 O(n) 是反转列表的最佳时间复杂度，但在之前的解决方案中存在大量资源成本。就像现在一样，reverse 必须为临时列表上的每个推送方法分配新节点。我们 可以避免完全使用临时列表，并通过操作每个节点的 next指针来反转列表。代码最终变得更加复杂，但我们在性能方面获得了相当大的好处。
将 reverse 方法更新为以下内容：
mutating func reverse() {
tail = head
var prev = head
var current = head?.next
prev?.next = nil
// more to come...
}
我们首先分配头到尾。接下来，创建两个引用——prev 和 current——来跟踪遍历。该策略相当简单：每个节点都指向列表中的下一个节点。我们将遍历列表并使每个节点都指向前一个节点：
从图中可以看出，它有点棘手。通过将 current指向 prev，我们失去了指向列表其余部分的链接。因此，我们需要管理第三个指针。在 reverse方法的底部添加以下内容：
while current != nil {
let next = current?.next
current?.next = prev
prev = current
current = next
}
每次执行反转时，都会创建对下一个节点的新引用。在每个反转过程之后，我们将两个指针移动到接下来的两个节点。
一旦你完成了所有指针的反转，我们将把头设置到这个列表的最后一个节点。在 reverse 方法的末尾添加以下内容：
head = prev
通过在 Playground 页面底部编写以下代码来测试反向方法：
example(of: "reversing a list") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Original list: \(list)")
list.reverse()
print("Reversed list: \(list)")
}
我们应该看到以下输出：
---Example of reversing a list---
Original list: 1 -> 2 -> 3
Reversed list: 3 -> 2 -> 1
新的反转方法的时间复杂度仍然是 O(n)，与前面讨论的简单实现相同。但是，我们不需要使用临时列表或分配新的 Node 对象，这显着提高了该算法的性能。
问题 4 解决方案
解决这个问题的方法是不断地从两个排序列表中抽取节点，并将它们添加到一个新列表中。由于这两个列表已排序，因此我们可以比较两个列表的下一个节点，看看哪一个应该是下一个添加到新列表中的节点。
我们将首先检查一个或两个列表为空的情况。将以下内容添加到 mergeSorted：
guard !left.isEmpty else {
return right
}
guard !right.isEmpty else {
return left
}
var newHead: Node<T>?
如果一个为空，则返回另一个。我们还引入了一个新的引用来保存 Node 对象的排序列表。策略是将左右的节点按排序顺序合并到newHead上。
在newHead下面写下：
// 1
var tail: Node<T>?
var currentLeft = left.head
var currentRight = right.head
// 2
if let leftNode = currentLeft, let rightNode = currentRight {
if leftNode.value < rightNode.value {
newHead = leftNode
currentLeft = leftNode.next
} else {
newHead = rightNode
currentRight = rightNode.next
}
tail = newHead
}
- 创建一个指向要添加到的新列表尾部的指针。这允许恒定时间的追加操作。
2.你比较left和right的第一个节点来分配newHead。
合并
接下来，我们需要遍历左右，挑选要添加的节点以确保新列表已排序。将以下内容添加到函数末尾：
// 1
while let leftNode = currentLeft, let rightNode = currentRight {
// 2
if leftNode.value < rightNode.value {
tail?.next = leftNode
currentLeft = leftNode.next
} else {
tail?.next = rightNode
currentRight = rightNode.next
}
tail = tail?.next
}
while 循环将继续，直到列表之一到达末尾。
很像以前，我们比较节点以找出连接到尾部的节点。
由于此循环同时依赖于 currentLeft 和 currentRight，因此即使节点保留在任一列表中，它也会终止。
添加以下内容来处理剩余的节点：
if let leftNodes = currentLeft {
tail?.next = leftNodes
}
if let rightNodes = currentRight {
tail?.next = rightNodes
}
这会附加节点的其余部分。
总结一下，我们实例化一个新列表。无需使用 append 或 insert 方法将元素插入列表，我们只需直接设置列表头部和尾部的引用：
var list = LinkedList<T>()
list.head = newHead list.tail = {
while let next = tail?.next {
tail = next
}
return tail
}()
return list
在playground的底部写下以下内容：
example(of: "merging two lists") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
var anotherList = LinkedList<Int>()
anotherList.push(-1)
anotherList.push(-2)
anotherList.push(-3)
print("First list: \(list)")
print("Second list: \(anotherList)")
let mergedList = mergeSorted(list, anotherList)
print("Merged list: \(mergedList)")
}
执行代码，输出结果如下：
---Example of merging two lists---
First list: 1 -> 2 -> 3
Second list: -3 -> -2 -> -1
Merged list: -3 -> -2 -> -1 -> 1 -> 2 -> 3
该算法的时间复杂度为 O(m + n)，其中 m 是第一个列表中的节点数，n 是第二个列表中的节点数。
问题 5 的解决方案
此解决方案遍历列表，删除与要删除的元素匹配的所有节点。每次执行删除时，都需要重新连接前任节点和后继节点。虽然这可能会变得复杂，但练习这种技术是非常值得的。许多数据结构和算法将依赖于巧妙地使用指针算法来构建。
我们需要考虑几种情况。首先是清除列表前面的节点。
修剪头部
要考虑的第一种情况是列表的头部包含要删除的值。假设我们要从以下列表中删除 1：
我们希望你的新头指向 2。
在 remove 函数中写入以下内容：
while let head = head, head.value == value {
head = head?.next
}
我们首先处理列表头部包含我们要删除的值的情况。由于可能有一系列具有相同值的节点，因此我们我们可以使用 while 循环来确保将它们全部删除。
取消链接节点
像许多与链表相关的算法一样，我们将利用我们的指针算术技能来取消链接节点。在 remove 的底部写下以下内容：
var prev = head
var current = head?.next
while let currentNode = current {
guard currentNode.value != value else {
prev?.next = currentNode.next
current = prev?.next
continue
}
// more to come
}
我们需要使用两个指针遍历列表。如果需要删除节点，将触发保护语句的 else 块。
修改列表，以便绕过不想要的节点：
代码写到这里，while 语句可能永远不会终止。我们需要移动 prev和 current 指针。在 while 循环的底部，guard语句之后编写以下内容：
prev = current
current = current?.next
最后，我们将更新链表的尾部。当原始尾部是包含我们要删除的值的节点时，这是必要的。将以下内容添加到 removeAll的末尾：
tail = prev
在 Playground 页面的底部写下以下内容：
example(of: "deleting duplicate nodes") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(2)
list.push(1)
list.push(1)
list.removeAll(3)
print(list)
}
我们将会看到如下输出结果：
---Example of deleting duplicate nodes---
1 -> 1 -> 2 -> 2
该算法的时间复杂度为 O(n)，因为我们需要遍历所有元素。
| 上一章 | 目录 | 下一章 |
|---|
