数据结构与算法六：Linked Lists Challenges

2023-04-16 本文已影响0人 _浅墨_

在本章中，我们将通过五个常见场景，来巩固我们的数据结构知识。

挑战1：反向打印

创建一个以相反顺序打印链表节点的函数。例如：

1 -> 2 -> 3 -> nil

// should print out the following:
3
2
1

挑战2：找到中间节点

创建一个查找链表中间节点的函数。例如：

1 -> 2 -> 3 -> 4 -> nil
// middle is 3

1 -> 2 -> 3 -> nil
// middle is 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

解决方案

Challenge 1 解决方案

解决这个问题的一个直接方法是使用递归。由于递归允许我们构建调用堆栈，因此只需在调用堆栈展开时调用打印语句即可：

private func printInReverse<T>(_ node: Node<T>?) {

  // 1
  guard let node = node else { return }

  // 2
  printInReverse(node.next)
}

首先是终止递归的条件，如果 node 为 nil，则表示您已到达列表的末尾。
这是你的递归调用，调用与下一个节点相同的函数。

将 printInReverse 函数更新为：

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
}

在 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)，因为我们一次性遍历了列表。
快慢指针（The runner’s technique）有助于解决与链表相关的各种问题。

挑战 3 的解决方案

要反转链表，必须访问每个节点并更新其下一个引用。这是一项棘手的任务，因为需要管理对多个节点的多个引用。

一个简单的方法，我们可以通过使用 push 方法和一个新的临时列表来简单地反转列表。

更新 playground 中的代码：

extension LinkedList {

  mutating func reverse() {

    // 1
    let tmpList = LinkedList<Value>()
    for value in self {
      tmpList.push(value)
    }

    // 2
    head = tmpList.head
  }
}

首先将列表中的当前值 push 到新的 tmpList，这将以相反的顺序创建一个列表。
将列表的头部指向反向节点。

时间复杂度 O(n) ，短小精悍！

可是等等…

尽管 O(n) 是反转列表的最佳时间复杂度，但是这样的解决方案存在空间资源成本。

其实我们可以通过操纵每个节点的下一个指针来反转列表，从而避免使用临时列表：

mutating func reverse() {
  tail = head
  var prev = head
  var current = head?.next
  prev?.next = nil

  // more to come...
}

该策略相当简单：每个节点都指向列表中的下一个节点。我们将遍历列表并使每个节点指向前一个节点。

这似乎有点棘手。通过将 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 对象的排序列表。该策略是将 left 和 right 中的节点按排序顺序合并到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
}

创建一个指针指向要添加到的新列表的尾部。这允许恒定时间追加操作。
比较 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 循环会一直继续，直到列表之一到达末尾。
比较节点以找出连接到 tail 的节点。

继续添加以下内容：

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 的解决方案

此解决方案向下遍历列表，删除与要删除的元素匹配的所有节点。每次执行移除时，都需要将前驱节点与后继节点重新连接。虽然这可能变得复杂，但练习这种技巧是非常值得的。许多数据结构和算法依赖于巧妙使用指针算法来构建。

我们需要考虑几种情况。首先是清除列表前面的节点。

要考虑的第一种情况是列表的头部包含要删除的值。

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

我们需要使用两个指针遍历列表。如果需要删除节点，将触发 guard 语句的 else 块。

在 while 循环的底部，在 guard 语句之后写下以下内容：

prev = current
current = current?.next

最后，我们将更新链表的尾部。当原始尾部是包含我们要删除的值的节点时，这是必需的。

将以下内容添加到 removeAll 的末尾：

tail = prev