前言

有需要的同學(xué)可以訂閱專(zhuān)欄：Swift數(shù)據(jù)結(jié)構(gòu)和算法專(zhuān)題
代碼地址：Swift數(shù)據(jù)結(jié)構(gòu)和算法代碼

正文

在本章中，我們將了解鏈表的五個(gè)常見(jiàn)場(chǎng)景。與大多數(shù)問(wèn)題相比森枪，這些問(wèn)題相對(duì)容易栅炒，它們將有助于鞏固我們對(duì)數(shù)據(jù)結(jié)構(gòu)的了解莫杈。

打開(kāi)啟動(dòng)項(xiàng)目開(kāi)始蛙婴。解決如下問(wèn)題敷钾。

問(wèn)題一：反轉(zhuǎn)打印

創(chuàng)建一個(gè)以相反順序打印鏈表節(jié)點(diǎn)的函數(shù)宣谈。例如：

1 -> 2 -> 3 -> nil

// should print out the following: 
3 
2 
1

問(wèn)題 2：尋找中間節(jié)點(diǎn)

創(chuàng)建一個(gè)查找鏈表中間節(jié)點(diǎn)的函數(shù)愈犹。例如：

1 -> 2 -> 3 -> 4 -> nil 
// 中間是 3

1 -> 2 -> 3 -> nil 
// 中間是 2

問(wèn)題 3：反轉(zhuǎn)鏈表

創(chuàng)建一個(gè)反轉(zhuǎn)鏈表的函數(shù)。我們可以通過(guò)操作節(jié)點(diǎn)來(lái)實(shí)現(xiàn)這一點(diǎn)闻丑，以便它們?cè)诹硪粋€(gè)方向上鏈接漩怎。例如：

// before 
1 -> 2 -> 3 -> nil

// after 
3 -> 2 -> 1 -> nil

問(wèn)題 4：合并兩個(gè)列表

創(chuàng)建一個(gè)函數(shù)，該函數(shù)采用兩個(gè)排序的鏈表并將它們合并為一個(gè)排序的鏈表嗦嗡。我們的目標(biāo)是返回一個(gè)新的鏈表勋锤，其中包含按排序順序來(lái)自兩個(gè)列表的節(jié)點(diǎn)。我們可以假設(shè)排序順序是升序的侥祭。例如：

// list1 
1 -> 4 -> 10 -> 11

// list2 
-1 -> 2 -> 3 -> 6

// merged list 
-1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 10 -> 11

問(wèn)題 5：刪除所有事件

創(chuàng)建一個(gè)函數(shù)叁执，從鏈表中刪除所有出現(xiàn)的特定元素茄厘。該實(shí)現(xiàn)類(lèi)似于我們?yōu)殒湵韺?shí)現(xiàn)的 remove(at:) 方法。例如：

// original list 
1 -> 3 -> 3 -> 3 -> 4

// list after removing all occurrences of 3 
1 -> 4

解決方案

問(wèn)題1解決方案

解決此問(wèn)題的一種直接方法是使用遞歸徒恋。由于遞歸允許我們構(gòu)建調(diào)用堆棧蚕断，因此我們只需在調(diào)用堆棧展開(kāi)時(shí)調(diào)用打印語(yǔ)句。我們的第一個(gè)任務(wù)是遞歸遍歷到最后入挣。將以下輔助函數(shù)添加到我們的Playground：

 private func printInReverse<T>(_ node: Node<T>?) { 
  // 1 
  guard let node = node else { return } 

  // 2 
  printInReverse(node.next) 
 } 

• 1.我們首先從基本情況開(kāi)始：終止遞歸的條件亿乳。如果 node 為 nil，則表示我們已到達(dá)列表的末尾径筏。
• 2. 這是我們的遞歸調(diào)用葛假，調(diào)用與下一個(gè)節(jié)點(diǎn)相同的函數(shù)。

打印

我們添加打印語(yǔ)句的位置將決定我們是否以相反的順序打印列表滋恬。

將函數(shù)更新為以下內(nèi)容：

private func printInReverse<T>(_ node: Node<T>?) { 
  guard let node = node else { return } 
  printInReverse(node.next) 
  print(node.value) 
} 

任何代碼 只有在基本情況觸發(fā)之后（即聊训，在遞歸函數(shù)到達(dá)列表末尾之后）才調(diào)用遞歸調(diào)用之后。隨著遞歸語(yǔ)句的展開(kāi)恢氯，節(jié)點(diǎn)數(shù)據(jù)被打印出來(lái)带斑。

最后，我們需要從原始 printInReverse 函數(shù)中調(diào)用輔助方法勋拟。將其更新為如下所示：

func printInReverse<T>(_ list: LinkedList<T>) { 
  printInReverse(list.head) 
}

在 Playground頁(yè)面的底部寫(xiě)下以下內(nèi)容：

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

我們應(yīng)該看到以下輸出：

---Example of printing in reverse---
Original list: 1 -> 2 -> 3 
Printing in reverse:
3 
2 
1

該算法的時(shí)間復(fù)雜度為 O(n)勋磕，因?yàn)槲覀儽仨毐闅v列表的每個(gè)節(jié)點(diǎn)「颐遥空間復(fù)雜度同樣為 O(n)挂滓，因?yàn)槲覀冸[式使用函數(shù)調(diào)用堆棧來(lái)處理每個(gè)元素。

問(wèn)題 2 的解決方案

一種解決方案是讓兩個(gè)引用遍歷列表的節(jié)點(diǎn)啸胧，其中一個(gè)的速度是另一個(gè)的兩倍赶站。一旦較快的參考到達(dá)終點(diǎn)，較慢的參考將在中間纺念。將函數(shù)更新為以下內(nèi)容：

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 聲明中贝椿，將下一個(gè)節(jié)點(diǎn)綁定到 nextFast。如果有下一個(gè)節(jié)點(diǎn)陷谱，則快速更新到 nextFast 的下一個(gè)節(jié)點(diǎn)团秽，有效地遍歷列表兩次。慢速指針只更新一次叭首。這被稱(chēng)為跑步者的技術(shù)习勤。

在 Playground頁(yè)面底部寫(xiě)下以下內(nèi)容：

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

你應(yīng)該看到以下輸出：

---Example of getting the middle node---
1 -> 2 -> 3 
2 -> 3

該算法的時(shí)間復(fù)雜度為 O(n)，因?yàn)槲覀円淮伪闅v了列表焙格。

問(wèn)題3的解決方案

要反轉(zhuǎn)鏈表图毕，我們必須訪問(wèn)每個(gè)節(jié)點(diǎn)并更新下一個(gè)引用以指向另一個(gè)方向。這可能是一項(xiàng)棘手的任務(wù)眷唉，因?yàn)槲覀冃枰芾韺?duì)多個(gè)節(jié)點(diǎn)的多個(gè)引用予颤。簡(jiǎn)單的方法 我們可以使用 push方法和一個(gè)新的臨時(shí)列表輕松地反轉(zhuǎn)列表囤官。更新 Playground中的代碼：

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

• 1. 首先將列表中的當(dāng)前值推送到新的 tmpList。這將以相反的順序創(chuàng)建一個(gè)列表蛤虐。
• 2. 我們將列表的頭部指向反向節(jié)點(diǎn)党饮。

O(n) 時(shí)間復(fù)雜度。

雖然 O(n) 是反轉(zhuǎn)列表的最佳時(shí)間復(fù)雜度驳庭，但在之前的解決方案中存在大量資源成本刑顺。就像現(xiàn)在一樣，reverse 必須為臨時(shí)列表上的每個(gè)推送方法分配新節(jié)點(diǎn)饲常。我們 可以避免完全使用臨時(shí)列表蹲堂，并通過(guò)操作每個(gè)節(jié)點(diǎn)的 next指針來(lái)反轉(zhuǎn)列表。代碼最終變得更加復(fù)雜贝淤，但我們?cè)谛阅芊矫娅@得了相當(dāng)大的好處柒竞。

將 reverse 方法更新為以下內(nèi)容：

mutating func reverse() {
  tail = head 
  var prev = head 
  var current = head?.next 
  prev?.next = nil
  // more to come...
}

我們首先分配頭到尾。接下來(lái)播聪，創(chuàng)建兩個(gè)引用——prev 和 current——來(lái)跟蹤遍歷朽基。該策略相當(dāng)簡(jiǎn)單：每個(gè)節(jié)點(diǎn)都指向列表中的下一個(gè)節(jié)點(diǎn)。我們將遍歷列表并使每個(gè)節(jié)點(diǎn)都指向前一個(gè)節(jié)點(diǎn)：

從圖中可以看出离陶，它有點(diǎn)棘手稼虎。通過(guò)將 current指向 prev，我們失去了指向列表其余部分的鏈接枕磁。因此渡蜻，我們需要管理第三個(gè)指針术吝。在 reverse方法的底部添加以下內(nèi)容：

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

每次執(zhí)行反轉(zhuǎn)時(shí)计济，都會(huì)創(chuàng)建對(duì)下一個(gè)節(jié)點(diǎn)的新引用。在每個(gè)反轉(zhuǎn)過(guò)程之后排苍，我們將兩個(gè)指針移動(dòng)到接下來(lái)的兩個(gè)節(jié)點(diǎn)沦寂。

一旦你完成了所有指針的反轉(zhuǎn)，我們將把頭設(shè)置到這個(gè)列表的最后一個(gè)節(jié)點(diǎn)淘衙。在 reverse 方法的末尾添加以下內(nèi)容：

head = prev

通過(guò)在 Playground 頁(yè)面底部編寫(xiě)以下代碼來(lái)測(cè)試反向方法：

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

我們應(yīng)該看到以下輸出：

---Example of reversing a list---
Original list: 1 -> 2 -> 3 
Reversed list: 3 -> 2 -> 1

新的反轉(zhuǎn)方法的時(shí)間復(fù)雜度仍然是 O(n)传藏，與前面討論的簡(jiǎn)單實(shí)現(xiàn)相同。但是彤守，我們不需要使用臨時(shí)列表或分配新的 Node 對(duì)象毯侦，這顯著提高了該算法的性能。

問(wèn)題 4 解決方案

解決這個(gè)問(wèn)題的方法是不斷地從兩個(gè)排序列表中抽取節(jié)點(diǎn)具垫，并將它們添加到一個(gè)新列表中侈离。由于這兩個(gè)列表已排序，因此我們可以比較兩個(gè)列表的下一個(gè)節(jié)點(diǎn)筝蚕，看看哪一個(gè)應(yīng)該是下一個(gè)添加到新列表中的節(jié)點(diǎn)卦碾。

我們將首先檢查一個(gè)或兩個(gè)列表為空的情況铺坞。將以下內(nèi)容添加到 mergeSorted：

guard !left.isEmpty else { 
  return right 
}

guard !right.isEmpty else { 
  return left 
}

var newHead: Node<T>?

如果一個(gè)為空，則返回另一個(gè)洲胖。我們還引入了一個(gè)新的引用來(lái)保存 Node 對(duì)象的排序列表济榨。策略是將左右的節(jié)點(diǎn)按排序順序合并到newHead上。

在newHead下面寫(xiě)下：

// 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. 創(chuàng)建一個(gè)指向要添加到的新列表尾部的指針绿映。這允許恒定時(shí)間的追加操作擒滑。

2.你比較left和right的第一個(gè)節(jié)點(diǎn)來(lái)分配newHead。

合并

接下來(lái)绘梦，我們需要遍歷左右橘忱，挑選要添加的節(jié)點(diǎn)以確保新列表已排序。將以下內(nèi)容添加到函數(shù)末尾：

// 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 循環(huán)將繼續(xù)卸奉，直到列表之一到達(dá)末尾钝诚。

2. 很像以前，我們比較節(jié)點(diǎn)以找出連接到尾部的節(jié)點(diǎn)榄棵。

由于此循環(huán)同時(shí)依賴(lài)于 currentLeft 和 currentRight凝颇，因此即使節(jié)點(diǎn)保留在任一列表中，它也會(huì)終止疹鳄。

添加以下內(nèi)容來(lái)處理剩余的節(jié)點(diǎn)：

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

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

這會(huì)附加節(jié)點(diǎn)的其余部分拧略。

總結(jié)一下，我們實(shí)例化一個(gè)新列表瘪弓。無(wú)需使用 append 或 insert 方法將元素插入列表垫蛆，我們只需直接設(shè)置列表頭部和尾部的引用：

var list = LinkedList<T>()

list.head = newHead list.tail = {

  while let next = tail?.next {

    tail = next
}

return tail 
}() 
return list

在playground的底部寫(xiě)下以下內(nèi)容：

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

執(zhí)行代碼，輸出結(jié)果如下：

---Example of merging two lists---
First list: 1 -> 2 -> 3 
Second list: -3 -> -2 -> -1 
Merged list: -3 -> -2 -> -1 -> 1 -> 2 -> 3

該算法的時(shí)間復(fù)雜度為 O(m + n)腺怯，其中 m 是第一個(gè)列表中的節(jié)點(diǎn)數(shù)袱饭，n 是第二個(gè)列表中的節(jié)點(diǎn)數(shù)。

問(wèn)題 5 的解決方案

此解決方案遍歷列表呛占，刪除與要?jiǎng)h除的元素匹配的所有節(jié)點(diǎn)虑乖。每次執(zhí)行刪除時(shí)，都需要重新連接前任節(jié)點(diǎn)和后繼節(jié)點(diǎn)晾虑。雖然這可能會(huì)變得復(fù)雜疹味，但練習(xí)這種技術(shù)是非常值得的。許多數(shù)據(jù)結(jié)構(gòu)和算法將依賴(lài)于巧妙地使用指針?biāo)惴▉?lái)構(gòu)建帜篇。

我們需要考慮幾種情況糙捺。首先是清除列表前面的節(jié)點(diǎn)。

修剪頭部

要考慮的第一種情況是列表的頭部包含要?jiǎng)h除的值笙隙。假設(shè)我們要從以下列表中刪除 1：

我們希望你的新頭指向 2洪灯。

在 remove 函數(shù)中寫(xiě)入以下內(nèi)容：

while let head = head, head.value == value { 
  head = head?.next 
}

我們首先處理列表頭部包含我們要?jiǎng)h除的值的情況。由于可能有一系列具有相同值的節(jié)點(diǎn)逃沿，因此我們我們可以使用 while 循環(huán)來(lái)確保將它們?nèi)縿h除婴渡。

取消鏈接節(jié)點(diǎn)

像許多與鏈表相關(guān)的算法一樣幻锁，我們將利用我們的指針?biāo)阈g(shù)技能來(lái)取消鏈接節(jié)點(diǎn)。在 remove 的底部寫(xiě)下以下內(nèi)容：

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 
}

我們需要使用兩個(gè)指針遍歷列表边臼。如果需要?jiǎng)h除節(jié)點(diǎn)哄尔，將觸發(fā)保護(hù)語(yǔ)句的 else 塊。

修改列表柠并，以便繞過(guò)不想要的節(jié)點(diǎn)：

代碼寫(xiě)到這里岭接，while 語(yǔ)句可能永遠(yuǎn)不會(huì)終止。我們需要移動(dòng) prev和 current 指針臼予。在 while 循環(huán)的底部鸣戴，guard語(yǔ)句之后編寫(xiě)以下內(nèi)容：

prev = current 
current = current?.next

最后，我們將更新鏈表的尾部粘拾。當(dāng)原始尾部是包含我們要?jiǎng)h除的值的節(jié)點(diǎn)時(shí)窄锅，這是必要的。將以下內(nèi)容添加到 removeAll的末尾：

tail = prev

在 Playground 頁(yè)面的底部寫(xiě)下以下內(nèi)容：

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

我們將會(huì)看到如下輸出結(jié)果：

---Example of deleting duplicate nodes---
1 -> 1 -> 2 -> 2

該算法的時(shí)間復(fù)雜度為 O(n)缰雇，因?yàn)槲覀冃枰闅v所有元素入偷。