上期我们探讨了使用Swift如何破解数组、字符串、集合、字典相关的算法题。本期我们一起来讲讲用Swift如何实现链表以及链表相关的技巧。本期主要内容有：
- 链表基本结构
- Dummy节点
- 尾插法
- 快行指针
基本结构
对于链表的概念，实在是基本概念太多，这里不做赘述。我们直接来实现链表节点。
|
1 2 3 4 5 6 7 8 9 |
class ListNode { var val: Int var next: ListNode? init(_ val: Int) { self.val = val self.next = nil } } |
有了节点，就可以实现链表了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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大的节点），最后再把左右两边拼起来。
思路有了，再把题目抽象一下，就是要实现这样一个函数：
|
1 |
func partition(head: ListNode?, _ x: Int) -> ListNode? {} |
即我们有给定链表的头节点，有给定的x值，要求返回新链表的头结点。接下来我们要想：怎么处理左边？怎么处理右边？处理完后怎么拼接？
先来看怎么处理左边。我们不妨把这个题目先变简单一点：
给一个链表和一个值x，要求只保留链表中所有小于x的值，原链表的节点顺序不能变。
例：1->5->3->2->4->2，给定x = 3。则我们要返回 1->2->2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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 } return dummy.next } |
现在我们解决了左边，右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下：
|
t; 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
}
|
