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

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

你的第一项任务是递归遍历到最后。在你的plyground上添加下面这个辅助函数。

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

测试一下吧!

在plyground页面的底部写下以下内容。

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的下一个节点，实际上是对列表进行了两次穿越。慢速指针只被更新一次。这就是所谓的 "跑步者 "技术。

试试吧!

在plyground页面的底部写下以下内容。

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方法和一个新的临时列表来倒置一个列表，这很简单。更新plyground上的代码。

extension LinkedList {

  mutating func reverse() { 
    // 1 
    let tmpList = LinkedList<Value>()
    for value in self { 
      tmpList.push(value) 
    } 
  
    // 2 
    head = tmpList.head
  }
}

1. 首先，你要把列表中的当前值推到一个新的tmpList中。这将创建一个相反顺序的列表。

2. 你把列表的头部指向反转的节点。

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

但是等等...

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

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

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

  // more to come...
}

首先，你把头分配给尾。接下来，你创建了两个引用--prev和current--来跟踪遍历。这个策略是相当直接的：每个节点都指向列表中的下一个节点。你要遍历列表，让每个节点都指向前一个节点。

正如你从图中看到的，这变得有点棘手。通过将当前节点指向上一个节点，你就失去了与列表中其他节点的联系。因此，你需要管理第三个指针。在反向方法的底部添加以下内容。

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

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

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

head = prev

试试吧!

通过在plyground页面的底部写下以下内容来测试反向方法。

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。

合并

接下来，你需要遍历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
}

1. while循环将继续进行，直到列表中的一个到达终点。

2. 和之前一样，你比较节点，找出哪个节点要连接到尾部。

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

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

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

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

这将追加其余的节点。

为了收尾，你实例化了一个新的 list。你不使用append或insert方法向列表插入元素，而是直接设置列表的头部和尾部的引用。

var list = LinkedList<T>()

list.head = newHead 
list.tail = {
  while let next = tail?.next {
    tail = next
  }
  return tail 
}() 
return list

试试吧!

在plyground的底部写下以下内容。

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 
}

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

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

继续旅行...

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

prev = current 
current = current?.next

最后，你要更新链表的尾部。当原来的尾部是一个包含你想删除的值的节点时，这是必要的。在 removeAll 的末尾添加以下内容。

tail = prev

就这样实现了!

试试吧!

在plyground页面的底部写下以下内容。

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)，因为你需要遍历所有的元素。

---

上一章	目录	下一章