上期我们探讨了使用Swift如何破解数组、字符串、集合、字典相关的算法题。本期我们一起来讲讲用Swift如何实现链表以及链表相关的技巧。本期主要内容有：
- 链表基本结构
- Dummy节点
- 尾插法
- 快行指针
基本结构
对于链表的概念，实在是基本概念太多，这里不做赘述。我们直接来实现链表节点。
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
有了节点，就可以实现链表了。
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
}
}
}
有了上面的基本操作，我们来看如何解决复杂的问题。
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
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节点，它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个，它有可能是原链表的第一个节点，可能在原链表的中间，也可能在最后，甚至可能不存在（nil）。而Dummy节点的引入可以巧妙的涵盖所有以上情况，我们可以用dummy.next方便得返回最终需要的头结点。
现在我们解决了左边，右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下：
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
// 引入Dummy节点
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，这是为了防止链表循环指向构成环，是必须的但是很容易忽略的一步。
刚才我们提到了环，那么怎么检测链表中是否有环存在呢？
快行指针
笔者理解快行指针，就是两个指针访问链表，一个在前一个在后，或者一个移动快另一个移动慢，这就是快行指针。所以如何检测一个链表中是否有环？用两个指针同时访问链表，其中一个的速度是另一个的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节点，因为有可能我们要删除的是头结点。
总结
这次我们用Swift实现了链表的基本结构，并且实战了链表的几个技巧。在结尾处，我还想强调一下Swift处理链表问题的两个细节问题：
- 一定要注意头结点可能就是nil。所以给定链表，我们要看清楚head是不是optional，在判断是不是要处理这种边界条件。
- 注意每个节点的next可能是nil。如果不为nil，请用"!"修饰变量。在赋值的时候，也请注意"!"将optional节点传给非optional节点的情况。
