前言

有需要的同学可以订阅专栏：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，则表示我们已到达列表的末尾。
• 2. 这是我们的递归调用，调用与下一个节点相同的函数。

打印

我们添加打印语句的位置将决定我们是否以相反的顺序打印列表。

将函数更新为以下内容：

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 
 } 
} 

• 1. 首先将列表中的当前值推送到新的 tmpList。这将以相反的顺序创建一个列表。
• 2. 我们将列表的头部指向反向节点。

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
}

1. 创建一个指向要添加到的新列表尾部的指针。这允许恒定时间的追加操作。

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
}

1. while 循环将继续，直到列表之一到达末尾。

2. 很像以前，我们比较节点以找出连接到尾部的节点。

由于此循环同时依赖于 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)，因为我们需要遍历所有元素。