基础概念
链表
节点
链表中每一个元素称为结点，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（单向链表一个；双向链表两个）
链表的分类
单链表 每一个节点只包含一个指向链表中下一个节点的指针（引用）。
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
双链表 每个节点包含两个指针（引用），一个指向前一个节点，一个指向后一个节点。
+--------+ +--------+ +--------+ +--------+
| |--->| |--->| |--->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<---| |<---| |<---| |
+--------+ +--------+ +--------+ +--------+
通常我们用 head 和 tail 指针来记录链表的头和尾。
+--------+ +--------+ +--------+ +--------+
head --->| |--->| |--->| |--->| |---> nil
| node 0 | | node 1 | | node 2 | | node 3 |
nil <---| |<---| |<---| |<---| |<--- tail
+--------+ +--------+ +--------+ +--------+
注意，最后一个节点的“下一个”指针是nil，第一个节点的“前一个”指针也是nil。
链表和数组的比较
- 数组内存上是连续的存储空间，链表内存地址可以是不连续的，内存利用率高，链表由于增加了结点的指针域，空间开销比较大。
- 数据查询时，数组可以直接通过下标迅速访问数组中的元素。而链表则需要从第一个元素开始一直找到需要的元素位置，显然，数组的查询效率会比链表的高
- 当进行增加或删除元素时，在数组中增加或删除一个元素，需要移动大量元素，在内存中空出一个元素的空间。而链表只需改动元素中的指针即可实现增加或删除元素，链表的增删效率比数组高。
代码
首先定义一个描述节点的类型：
public class ListNode <T> {
var value: T
var next: LinkedListNode?
weak var previous: LinkedListNode?
public init(value: T) {
self.value = value
}
}
注意： 为避免循环强引用，我们声明previous指针为弱引用。 如果链表中有一个节点A后面跟着节点B，那么A指向B，而B指向A。 在某些情况下，即使在删除节点后，此循环强引用也可能导致节点保持活动状态。 所以我们使其中一个指针weak来打破循环。
构建 LinkedList
public class LinkedList<T> {
public typealias Node = ListNode<T>
//头指针
private var head: Node?
//尾指针
private var tail: Node?
//是否空链表
public var isEmpty: Bool {
return head == nil
}
//链表中的第一个节点
public var first: Node? {
return head
}
//链表中的最后一个节点
public var last: Node? {
return tail
}
//链表的结点数量
public var count: Int = 0
//新节点添加到链表的末尾
public func append(value: T) {
let newNode = Node(value: value)
if let tailNode = tail {
tailNode.next = node
node.previous = tailNode
}else {
head = newNode
}
tail = newNode
count += 1
}
/// 在链表中的特定索引处找到节点
/// - Parameter index: 索引
/// - Returns: 返回结果
public func nodeAt(index: Int) -> Node? {
guard index >= 0 else {
return nil
}
var i = index
var node = head
while node != nil {
if i == 0 {
return node
}
node = node?.next
i -= 1
}
return nil
}
/// node节点后插入值为val的节点
/// - Parameter node: 目标节点啊
/// - Parameter val: 插入的节点的值
func insert(node: Node, val: T) {
let newNode = Node(value: val)
newNode.next = node.next
node.next = newNode
}
/// 链表清空
public func removeAll() {
self.head = nil
self.tail = nil
}
/// 删除一个节点（双向链表）
/// - Parameter node: 要删除的节点
public func dLLRemove(node: Node) {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
}
/// 删除一个节点（单向链表）
/// - Parameter node: 要删除的节点
/// 当需要删除一个节点p时，只需要将p的前一个节点的next赋为p->next,但是由于是单向的，只知道p，无法知道p前一个节点，所以需要转换思路。将p下一个的节点覆盖到p节点即可，这样就等效于将p删除了。
func sLLRemove(node: Node) {
if let next = node.next {
node.value = next.value
node.next = next.next
} else {
self.pop()
}
}
/// 去掉最后一个节点
public func pop() -> Node? {
/// 存在最后一个节点
if let last = tail {
/// 存在最后一个节点的前一个节点
if let lp = last.previous {
lp.next = nil
tail = lp
} else {/// 不存在
head = nil
tail = nil
}
count -= 1
}
tail?.previous = nil
tail?.next = nil
return tail
}
}
练习：1. 判断是否是循环链表
快慢指针
解题思路：慢指针每次移动一步，快指针每次移动两步，如果存在环，那么两个指针一定会在环内相遇。
找到环的入口点
解题思路：两个指针相遇后，让其中一个指针回到链表的头部，另一个指针在原地，同时往前每次走一步，当它们再次相遇时，就是在环路的入口点。
找出环开始的节点证明
image.png
根据上图，我们可以得到下面的关系式：
w + n + y = 2 (w + y)
经过化简，我们可以得到：w = n - y;
这种情况下，我们就可以直接把 p2 放在 pHead 处，然后让两个指针以同样的速度走，那么，两者下一次就一定在入口节点相遇了。
extension LinkedList {
/// 找到循环链表的一个相同节点
/// - Returns: 返回结果
func fineMeetNode() -> Node? {
guard let h = head else {
return nil
}
var fast: Node? = h
var slow: Node? = h
while (fast?.value != nil && fast?.next?.value != nil) { //两个变量赛跑，找出相遇的节点
fast = (fast?.next?.next)!
slow = slow?.next!
if (fast!.value == slow!.value) {
return slow
}
}
return nil
}
/// 找到循环链表的入口
/// - Returns: 返回结果
func findCycleEntrance() -> Node? {
guard var meetNode = self.fineMeetNode() else {
return nil
}
while meetNode.value != self.head?.value {
meetNode = meetNode.next!
self.head = self.head?.next
}
return meetNode
}
}
练习：2. 删除链表中倒数第n个节点
题目描述：删除单链表倒数第 n 个节点，1 <= n <= length，尽量在一次遍历中完成。
解题思路：经典的双指针法。定义两个指针，第一个指针从链表的头指针开始遍历向前走n-1步，第二个指针保持不动，从第n步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针的距离保持在n-1，当第一个指针到达链表的尾节点时，第二个指针刚好指向倒数第n个节点。
/// 打印协议
extension LinkedList: CustomStringConvertible where T: CustomStringConvertible {
public var description: String {
/// 头节点
var head = self.head
var result: String = ""
/// 当前节点不等于nil
while head != nil {
result += head?.value.description ?? ""
head = head?.next
if head != nil {
result += "->"
}
}
return result
}
}
/// 移除倒数第n个节点
extension LinkedList where T == Int {
func removeNthFromEnd(head: Node<T>?, _ n: Int) -> ListNode<T>?{
guard let head = head else {
return nil
}
let dummy = Node<Int>(value: 0)
dummy.next = head
var first: Node? = dummy
var second: Node? = dummy
/// 设置后一个节点的初始位置
for _ in 0..<n {
first = first?.next
}
/// 同时移动前后节点
while first != nil, first?.next != nil {
first = first?.next
second = second?.next
}
// 删除节点
second?.next = second?.next?.next
return dummy.next
}
}
let ll = LinkedList<Int>()
ll.append(value: 1)
ll.append(value: 2)
ll.append(value: 3)
ll.append(value: 4)
ll.append(value: 5)
ll.removeNthFromEnd(head: ll.head, 2)
let rrr = ll.description
// 结果： "1->2->3->5"
练习：3. 翻转单链表
题目描述：输出一个单链表的逆序反转后的链表。
方案一：
迭代：在链表第一个和第二个元素断开链表，保存后半段，前半段拼在新head前方，然后赋值给新head：具体如下面示意
p: a -> b -> c -> d -> e -> nil
newHead = nil
temp = p.next temp: b -> c -> d -> e -> nil
p.next = newHead p: a -> nil
newHead = p newHead: a -> nil
p = temp p: b -> c -> d -> e -> nil
temp = p.next temp: c -> d -> e -> nil
p.next = newHead p: b -> a -> nil
newHead = p newHead: b -> a -> nil
p = temp p: c -> d -> e -> nil
...
newHead: d -> d -> c -> b -> a -> nil
-----------------------------------------------------------------------------------
/// 返回反转后头结点
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var newHead: ListNode? = nil
var p = head
while p != nil {
let tmp = p?.next
p?.next = newHead
newHead = p
p = tmp
}
return newHead
}
方案二：
递归：递归找到最后一个节点作为新链表的头节点，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
let newHead = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return newHead
}
