7.链接表的挑战¶

在这一章中，你将通过链接列表的五种常见情况。与大多数挑战相比，这些问题相对容易，它们将有助于巩固你对数据结构的认识。

打开启动器项目开始。在该项目中，你会发现以下挑战。

挑战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

解决方案¶

挑战1的解决方案¶

解决这个问题的一个直接方法是使用递归法。由于递归允许你建立一个调用栈，你只需要在调用栈展开时调用print语句。

你的第一个任务是递归遍历到最后。在你的Playground上添加以下辅助函数：

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

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

  // 2
  printInReverse(node.next)
}

你首先从base case开始：终止递归的条件。如果node是nil，那么意味着你已经到达了列表的末端。
这是你的递归调用，用下一个节点调用同一个函数。

打印¶

你在哪里添加print语句将决定你是否按相反顺序打印列表。

将该函数更新为以下内容：

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。如果有下一个节点，你就把fast更新到nextFast的下一个节点，有效地遍历列表两次。slow指针只被更新一次。这就是所谓的runner技术。

试试吧!¶

在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
    let tmpList = LinkedList<Value>()
    for value in self {
      tmpList.push(value)
    }

    // 2
    head = tmpList.head
  }
}

你首先将你的列表中的当前值推送到一个新的tmpList。这将创建一个相反顺序的列表。
你把列表的head指向反转的节点。

O(n)时间复杂度，又短又好!

但是等等...¶

虽然O(n)是反转列表的最佳时间复杂度，但在之前的解决方案中，有一个很大的资源成本。就像现在这样，reverse将不得不为临时列表上的每个push方法分配新的节点。你可以完全避免使用临时列表，通过操作每个节点的next指针来反转列表。这段代码最终会变得更加复杂，但你在性能方面获得了相当大的好处。

将反向方法更新为以下内容：

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

  // more to come...
}

你首先把head分配给tail。接下来，你创建了两个引用 - prev和current，以记录遍历的情况。这个策略是相当直接的：每个节点都指向列表的下一个节点。你要遍历列表，让每个节点指向前一个节点：

正如你从图中看到的，它变得有点棘手。通过将current指向prev，你已经失去了与列表其他部分的联系。因此，你需要管理第三个指针。在reverse方法的底部添加以下内容：

while current != nil {
  let next = current?.next
  current?.next = prev
  prev = current
  current = next
}

每次你执行反转，你都会创建一个新的引用到下一个节点。在每次反转过程后，你将两个指针移到下两个节点。

一旦你完成了对所有指针的反转，你将把head设置为这个列表的最后一个节点。在reverse方法的末尾添加以下内容：

head = prev

试试吧!¶

通过在Playground页面的底部写下以下内容来测试reverse方法：

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

你的新的reverse方法的时间复杂度仍然是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
}

你创建了一个指向你要添加的新列表的tail的指针。这样可以实现恒定时间的追加操作。
比较left和right的第一个节点来分配newHead。

合并¶

接下来，你需要遍历left和right，精挑细选要添加的节点，确保新的列表是排序的。在函数的末尾添加以下内容：

// 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。

因为这个循环依赖于currentLeft和currentRight，所以即使这两个列表上还有节点，它也会终止。

添加以下内容来处理剩余的节点：

if let leftNodes = currentLeft {
  tail?.next = leftNodes
}

if let rightNodes = currentRight {
  tail?.next = rightNodes
}

这将追加剩余的节点。

为了收尾，你实例化了一个新的列表。你没有使用append或insert方法来插入元素到列表中，而是直接设置列表的head和tail的引用：

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

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

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

修剪`head`¶

要考虑的第一种情况是当列表的头部包含你想删除的值时。假设你想从下面的列表中删除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
}

你需要使用两个指针来遍历这个列表。guard语句的else块会在有必要删除节点时触发。

你修改列表，使你绕过你不想要的节点：

继续旅行...¶

你能看出缺少什么吗？就像现在这样，while语句可能永远不会终止。你需要移动prev和current指针。在while循环的底部，在guard语句之后写下以下内容：

prev = current
current = current?.next

最后，你要更新链表的tail。当原始尾巴是包含你想删除的值的节点时，这是必要的。在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)，因为你需要遍历所有的元素。

7.链接表的挑战¶

挑战1：反向打印¶

挑战2：寻找中间节点¶

挑战3：反转一个链表¶

挑战4：合并两个列表¶

挑战5：删除所有出现的元素¶

解决方案¶

挑战1的解决方案¶

打印¶

测试一下吧!¶

挑战2的解决方案¶

试试吧!¶

挑战3的解决方案¶

简单的方法¶

但是等等...¶

试试吧!¶

挑战4的解决方案¶

设置¶

合并¶

试试吧!¶

挑战5的解决方案¶

修剪head¶

解除节点的链接¶

继续旅行...¶

试试吧!¶

修剪`head`¶