用Swift实现链表

基本概念

链表节点

class ListNode { 
  var val: Int 
  var next: ListNode? 

  init(_ val: Int) {
    self.val = val
  }
}

有了节点，就可以实现链表了

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

  // 头插法 
  func appendToHead(_ val: Int) {
    let node = ListNode(val)

    if let _ = head {
      node.next = head
    } else {
      tail = node
    }

    head = node
  }

  // 尾插法
  func appendToTail(_ val: Int) {
    let node = ListNode(val)

    if let _ = tail {
      tail!.next = node
    } else {
      head = node
    }

    tail = node
  }
}

有了上面的基本操作，我们来看如何解决复杂的问题。

Dummy 节点和尾插法

先来看下面一道题目。

给一个链表和一个值 x，要求将链表中所有小于 x 的值放到左边，所有大于等于 x 的值放到右边。原链表的节点顺序不能变。

例：1->5->3->2->4->2，给定x = 3。则我们要返回1->2->2->5->3->4

这题要先处理左边（比 x 小的节点），然后再处理右边（比 x 大的节点），最后再把左右两边拼起来。

把题目抽象一下，就是要实现这样一个函数：

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

即我们有给定链表的头节点，有给定的x值，要求返回新链表的头结点。接下来：怎么处理左边？怎么处理右边？处理完后怎么拼接？

先来看怎么处理左边。

给一个链表和一个值 x，要求只保留链表中所有小于 x 的值，原链表的节点顺序不能变。

例：1->5->3->2->4->2，给定x = 3。则我们要返回 1->2->2

我们只要采用尾插法，遍历链表，将小于 x 值的节点接入新的链表即可。代码如下：

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

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

  // 防止构成环 
  pre.next = nil
  return dummy.next 
}

注意，上面的代码我们引入了 Dummy 节点，它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个，它有可能是原链表的第一个节点，可能在原链表的中间，也可能在最后，甚至可能不存在（nil）。而 Dummy 节点的引入可以巧妙的涵盖所有以上情况，我们可以用 dummy.next 方便得返回最终需要的头结点。

现在我们解决了左边，右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下：

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
  // 引入Dummy节点 
  let prevDummy = ListNode(0), postDummy = ListNode(0) 
  var prev = prevDummy, 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，这是为了防止链表循环指向构成环，是必须的但是很容易忽略的一步。
刚才我们提到了环，那么怎么检测链表中是否有环存在呢？

图片.png

快行指针

快行指针，就是两个指针访问链表，一个在前一个在后，或者一个移动快另一个移动慢，这就是快行指针。来看一道简单的面试题：

如何检测一个链表中是否有环？

答案是用两个指针同时访问链表，其中一个的速度是另一个的 2 倍，如果他们相等了，那么这个链表就有环了，这就是快行指针的实际使用。代码如下：

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 
}

再举一个快行指针一前一后的例子，看下面这道题。

删除链表中倒数第 n 个节点。例：1->2->3->4->5，n = 2。返回1->2->3->5。
注意：给定 n 的长度小于等于链表的长度。

解题思路依然是快行指针，这次两个指针移动速度相同。但是一开始，第一个指针（指向头结点之前）就落后第二个指针 n 个节点。接着两者同时移动，当第二个移动到尾节点时，第一个节点的下一个节点就是我们要删除的节点。代码如下：

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 

  // 设置后一个节点初始位置 
  for _ in 0 ..< n { 
    if post == nil { 
      break 
    }
    post = post!.next
  }

  // 同时移动前后节点 
  while post != nil && post!.next != nil { 
    prev = prev!.next
    post = post!.next
  }

  // 删除节点 
  prev!.next = prev!.next!.next

  return dummy.next 
}

这里还用到了 Dummy 节点，因为有可能我们要删除的是头结点。

总结

• 一定要注意头结点可能就是 nil。所以给定链表，我们要看清楚 head 是不是 optional，在判断是不是要处理这种边界条件。
• 注意每个节点的 next 可能是 nil。如果不为 nil，请用"!"修饰变量。在赋值的时候，也请注意"!"将 optional 节点传给非 optional 节点的情况。