上期我們探討了使用Swift如何破解數(shù)組、字符串、集合、字典相關(guān)的算法題。本期我們一起來講講用Swift如何實現(xiàn)鏈表以及鏈表相關(guān)的技巧。本期主要內(nèi)容有：

• 鏈表基本結(jié)構(gòu)
• Dummy節(jié)點
• 尾插法
• 快行指針

基本結(jié)構(gòu)

對于鏈表的概念，實在是基本概念太多，這里不做贅述。我們直接來實現(xiàn)鏈表節(jié)點。

class ListNode {
  var val: Int
  var next: ListNode?
  
  init(_ val: Int) {
    self.val = val
    self.next = nil
  }
}

有了節(jié)點，就可以實現(xiàn)鏈表了。

class List {
  var head: ListNode?
  var tail: ListNode?

  // 尾插法
  func appendToTail(_ val: Int) {
    if tail == nil {
      tail = ListNode(val)
      head = tail
    } else {
      tail!.next = ListNode(val)
      tail = tail!.next
    }
  }
  
  // 頭插法
  func appendToHead(_ val: Int) {
    if head == nil {
      head = ListNode(val)
      tail = head
    } else {
      let temp = ListNode(val)
      temp.next = head
      head = temp
    }
  }
}

有了上面的基本操作，我們來看如何解決復(fù)雜的問題。

Dummy節(jié)點和尾插法

話不多說，我們直接先來看下面一道題目。

給一個鏈表和一個值x，要求將鏈表中所有小于x的值放到左邊，所有大于等于x的值放到右邊。原鏈表的節(jié)點順序不能變。
例：1->5->3->2->4->2，給定x = 3。則我們要返回 1->2->2->5->3->4

直覺告訴我們，這題要先處理左邊（比x小的節(jié)點），然后再處理右邊（比x大的節(jié)點），最后再把左右兩邊拼起來。
思路有了，再把題目抽象一下，就是要實現(xiàn)這樣一個函數(shù)：

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {}

即我們有給定鏈表的頭節(jié)點，有給定的x值，要求返回新鏈表的頭結(jié)點。接下來我們要想：怎么處理左邊？怎么處理右邊？處理完后怎么拼接？
先來看怎么處理左邊。我們不妨把這個題目先變簡單一點：

給一個鏈表和一個值x，要求只保留鏈表中所有小于x的值，原鏈表的節(jié)點順序不能變。
例：1->5->3->2->4->2，給定x = 3。則我們要返回 1->2->2

我們只要采用尾插法，遍歷鏈表，將小于x值的節(jié)點接入新的鏈表即可。代碼如下：

func getLeftList(_ head: ListNode?, _ x: Int) -> ListNode? {
  let dummy = ListNode(0)
  var pre = dummy
  var node = head

  while node != nil {
    if node!.val < x {
      pre.next = node
      pre = node!
    }
    node = node!.next
  }

  node.next = nil
  return dummy.next
}

注意，上面的代碼我們引入了Dummy節(jié)點，它的作用就是作為一個虛擬的頭前結(jié)點。我們引入它的原因是我們不知道要返回的新鏈表的頭結(jié)點是哪一個，它有可能是原鏈表的第一個節(jié)點，可能在原鏈表的中間，也可能在最后，甚至可能不存在（nil）。而Dummy節(jié)點的引入可以巧妙的涵蓋所有以上情況，我們可以用dummy.next方便得返回最終需要的頭結(jié)點。
現(xiàn)在我們解決了左邊，右邊也是同樣處理。接著只要讓左邊的尾節(jié)點指向右邊的頭結(jié)點即可。全部代碼如下：

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
  // 引入Dummy節(jié)點
  let prevDummy = ListNode(0)
  var prev = prevDummy
  let postDummy = ListNode(0)
  var post = postDummy
        
  var node = head
  
  // 用尾插法處理左邊和右邊
  while node != nil {
    if node!.val < x {
      prev.next = node
      prev = node!
    } else {
      post.next = node
      post = node!
    }     
    node = node!.next
  }
  
  // 左右拼接
  post.next = nil
  prev.next = postDummy.next
        
  return prevDummy.next
}

注意這句post.next = nil，這是為了防止鏈表循環(huán)指向構(gòu)成環(huán)，是必須的但是很容易忽略的一步。
剛才我們提到了環(huán)，那么怎么檢測鏈表中是否有環(huán)存在呢？

快行指針

筆者理解快行指針，就是兩個指針訪問鏈表，一個在前一個在后，或者一個移動快另一個移動慢，這就是快行指針。所以如何檢測一個鏈表中是否有環(huán)？用兩個指針同時訪問鏈表，其中一個的速度是另一個的2倍，如果他們相等了，那么這個鏈表就有環(huán)了。代碼如下：

func hasCycle(_ head: ListNode?) -> Bool {
  var slow = head
  var fast = head
  
  while fast != nil && fast!.next != nil {
    slow = slow!.next
    fast = fast!.next!.next
    
    if slow === fast {
      return true
    }
  }
  
  return false
}

再舉一個快行指針一前一后的例子，看下面這道題。

刪除鏈表中倒數(shù)第n個節(jié)點。例：1->2->3->4->5，n = 2。返回1->2->3->5。
注意：給定n的長度小于等于鏈表的長度。

解題思路依然是快行指針，這次兩個指針移動速度相同。但是一開始，第一個指針（指向頭結(jié)點之前）就落后第二個指針n個節(jié)點。接著兩者同時移動，當?shù)诙€移動到尾節(jié)點時，第一個節(jié)點的下一個節(jié)點就是我們要刪除的節(jié)點。代碼如下：

func removeNthFromEnd(head: ListNode?, _ n: Int) -> ListNode? {
  guard let head = head else {
    return nil
  }
  
  let dummy = ListNode(0)
  dummy.next = head
  var prev: ListNode? = dummy
  var post: ListNode? = dummy
  
  // 設(shè)置后一個節(jié)點初始位置
  for _ in 0 ..< n {
    if post == nil {
      break
    }
    post = post!.next
  }
  
  // 同時移動前后節(jié)點
  while post != nil && post!.next != nil {
    prev = prev!.next
    post = post!.next
  }
  
  // 刪除節(jié)點
  prev!.next = prev!.next!.next
  
  return dummy.next
}

這里還用到了Dummy節(jié)點，因為有可能我們要刪除的是頭結(jié)點。

總結(jié)

這次我們用Swift實現(xiàn)了鏈表的基本結(jié)構(gòu)，并且實戰(zhàn)了鏈表的幾個技巧。在結(jié)尾處，我還想強調(diào)一下Swift處理鏈表問題的兩個細節(jié)問題：

• 一定要注意頭結(jié)點可能就是nil。所以給定鏈表，我們要看清楚head是不是optional，在判斷是不是要處理這種邊界條件。
• 注意每個節(jié)點的next可能是nil。如果不為nil，請用"!"修飾變量。在賦值的時候，也請注意"!"將optional節(jié)點傳給非optional節(jié)點的情況。