Swift - 链表的使用
2019-06-26 本文已影响0人
Longshihua
基本知识点
节点（Node）
public class Node<Value> {
var value: Value // 持有一个值
var next: Node? // 下一个节点
init(value: Value, next: Node? = nil) {
self.value = value
self.next = next
}
}
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
创建一个简单列表
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
print(node1)
输出：1 -> 2 -> 3
虽然这种方式可以创建链表，但是如果需要长链表的话，那么就变得不实用了。所以，一种普遍的方法就是创建链表来管理节点对象。
创建链表
public struct LinkedList<Value> {
var head: Node<Value>? //头结点
var tail: Node<Value>? //尾结点
init() {}
var isEmpty: Bool { //链表是否为空
return head == nil
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty List"
}
return String(describing: head)
}
}
结构体链表中拥有头尾节点两个属性，链表中的头尾节点是指链表的第一个节点和最后一个节点.
添加值到链表
这里有3种方式，每一种方式都有自己的独自性能特性：
push：在列表的前面添加值，即头插法
append：在列表的末尾添加值，即尾插法
insert(after:)：在列表中特定节点的后面添加值
- push
添加一个值到链表的最前面，我们使用push操作，也叫head-first insertion,时间复杂度为O(1)。在LikedList结构体中添加如下方法：
mutating func push(_ value: Value) {
head = Node(value: value, next: head)
if tail == nil { // 创建新节点，没有尾节点，头节点和尾节点指向同一个新节点
tail = head
}
}
如果我们添加一个节点到一个空链表，那么头尾节点都指向改新节点。简单使用一下：
var list = LinkedList<Int>()
list.push(4)
list.push(5)
list.push(6)
print(list) //输出结果：6 -> 5 -> 4
- append
拼接操作，即在链表的末尾添加一个值，也叫tail-end insertion，时间复杂度为O(1)。在LikedList结构体中添加如下方法：
mutating func append(_ value: Value) {
// 1
guard !isEmpty else {
push(value)
return
}
// 2
tail?.next = Node(value: value)
// 3
tail = tail?.next
}
代码很简单
1）判断链表是否为空，为空即执行push操作创建一个新的节点。
2）创建一个新节点，赋值为尾部节点的下一个节点，即将节点连接起来
3）因为是尾部拼接节点，所以新的节点将成为尾部节点
简单使用
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)
print(list) // 1 -> 2 -> 3
- insert(after:)
插入一个值到链表的具体位置，需要二步：
1）找到链表中具体的节点
func node(at index: Int) -> Node<Value>? {
//1
var currentNode = head
var currentIndex = 0
//2
while currentNode != nil && currentIndex < index {
currentNode = currentNode?.next
currentIndex += 1
}
return currentNode
}
上面代码是根据给定的位置，获取对应位置的节点，因为我们只能从列表的头节点开始访问，所以使用while循环遍历获取对应位置的节点，链表为空或者越界返回nil。
2）插入一个新的节点
//1 discardableResult关键字告诉调用者可以忽略返回值
@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
//2 判断插入的结点是否是尾结点，如果是尾结点，那么直接尾部拼接结点
guard tail !== node else {
append(value)
return tail!
}
//3 创建新的结点
//1）把当前结点的下一个结点作为新结点的下一个结点
//2）并把新结点作为当前结点的下一个结点
node.next = Node(value: value, next: node.next)
return node.next!
}
简单使用
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Before inserting: \(list)")
var middleNode = list.node(at: 1)!
for _ in 1...4 {
middleNode = list.insert(-1, after: middleNode)
}
print("After inserting: \(list)")
运行输出
Before inserting: 1 ->2 ->3
After inserting: 1 ->2 ->-1 ->-1 ->-1 ->-1 ->3
从链表中去除结点
有3种主要的方式去除结点：
pop：从链表的开始去除结点
removeLast：从链表的最后去除结点
remove(at:)：从链表的指定位置去除结点
- pop
public mutating func pop() -> Value? {
defer { // defer关键字表示延迟执行
head = head?.next // 头结点的下一个结点作为头结点
if isEmpty { // 如果链表为空，清空尾结点
tail = nil
}
}
return head?.value // 返回被去除的结点值
}
简单删除一个结点，时间复杂度为O(1)
简单使用
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("before popping list: \(list)")
let poppedValue = list.pop()
print("after popping list: \(list)")
print("popped value: " + String(describing: poppedValue))
运行输出
before popping list: 1 ->2 ->3
after popping list: 2 ->3
popped value: Optional(1)
- removeLast
@discardableResult
public mutating func removeLast() -> Value? {
// 1 如果头结点尾nil，直接返回nil
guard let head = head else {
return nil
}
// 2 头结点的下一个结点存在继续执行，不存在说明只有一个结点，等同于执行pop操作
guard head.next != nil else {
return pop()
}
// 3 引用头结点进行遍历查找最后结点
var prev = head
var current = head
while let next = current.next { // 当前结点的下一个结点是否存在
prev = current
current = next
}
// 4 将最后结点去除，因为pre是最后结点的上一个结点
prev.next = nil
tail = prev // 更新尾结点
return current.value
}
因为需要遍历整个链表，所以是相对耗时的，时间复杂度为O(n)
简单使用
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("before removing last node: \(list)")
let removedValue = list.removeLast()
print("after removing lasr node: \(list)")
print("removed value: " + String(describing: removedValue))
运行输出
before removing last node: 1 ->2 ->3
after removing lasr node: 1 ->2
removed value: Optional(3)
- remove(after:)
去除指定位置的结点操作。其实跟之前的插入结点到指定位置是类似的，需要先找到希望去除的结点，然后去除
@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
defer {
if node.next === tail { // 如果该结点的下一个结点是尾结点
tail = node // 当前结点设置为尾结点
}
node.next = node.next?.next // 去除node结点之后的结点
}
return node.next?.value // 返回node结点之后结点的值
}
简单使用
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("before removing at particular index: \(list)")
let index = 1
let node = list.node(at: index - 1)!
let removedValue = list.remove(after: node)
print("after removing at index \(index): \(list)")
print("removed value: " + String(describing: removedValue))
运行输出
before removing at particular index: 1 ->2 ->3
after removing at index 1: 1 ->3
removed value: Optional(2)
相关题
1、给出一个链表和一个值x，要求将链表中所有小于x的值放到左边，所有大于或等于x的值放到右边，并且原链表的结点顺序不能变。
例如：1->5->3->2->4->2，给定x=3，那么返回 1->2->2->5->3->4
思路：根据题目的意思，我们只需要遍历链表，然后将小于给定值的结点组成一个链表，大于给定值的结点组成一个链表，最后两个链表进行拼接即可。
实现
结点
class Node {
var value: Int
var next: Node?
init(_ value: Int) {
self.value = value
self.next = nil
}
}
extension ListNode: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) ->" + String(describing: next) + " "
}
}
链表
class List {
var head: ListNode?
var tail: ListNode?
// 尾插法
func appendToTail(_ value: Int) {
if tail == nil {
tail = ListNode(value)
head = tail
} else {
tail!.next = ListNode(value)
tail = tail!.next
}
}
// 头插法
func appendToHead(_ value: Int) {
if head == nil {
head = ListNode(value)
tail = head
} else {
let node = ListNode(value)
node.next = head // 当前结点的下一个结点为头结点
head = node // 头结点指向当前结点
}
}
}
在List中添加功能实现函数
func listSort(_ head: ListNode? , _ x : Int) -> ListNode? {
let leftDummy = ListNode(0), rightDummy = ListNode(0) //1
var left = leftDummy, right = rightDummy
var node = head
// 用尾插法处理左边和右边
while node != nil { //2
if node!.value < x { //3
left.next = node
left = node!
} else { //4
right.next = node
right = node!
}
node = node!.next //5
}
right.next = nil
// 左右拼接
left.next = rightDummy.next
// 返回假结点的下一个结点开始，即新链表
return leftDummy.next
}
1、创建两个假的结点，方便用于连接给定值左右两边的结点
2、判断当前结点是否存在，如果存在进行循环，获取结点值与给定值进行比较
3、如果当前结点值小于给定值就拼接到左结点之后，并移动指针指向末尾结点，方便后续继续添加结点
4、如果当前结点值大于给定值就拼接到右结点之后，并移动指针指向末尾结点
5、获取链表头结点的下一个结点继续循环，一直到链表末尾
使用
let list = List()
list.appendToTail(1)
list.appendToTail(5)
list.appendToTail(3)
list.appendToTail(2)
list.appendToTail(4)
list.appendToTail(2)
print(list.head!) //1 ->5 ->3 ->2 ->4 ->2
let newList = list.listSort(list.head, 3)
print(newList!) // 1 ->2 ->2 ->5 ->3 ->4
2、快行指针
快行指针就是两个指针访问链表，一个在前，一个在后，或者一个移动快，另一个移动慢。在处理链表的时候，我们经常用到两个指针遍历链表：previous 和 current，也就是current 比 previous 超前一个节点
1）如何检测一个链表中是否有环？
思路：使用两个指针同时访问链表，其中一个的速度是另一个的两倍，如果它们变成相等，那么这个链表就有环了。
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
}
2）删除链表中倒数第n个结点。例如：1->2->3->4->5，n=2,返回 1->2->3->5
注意：给定的n长度小于等于链表的长度
思路：两个指针的移动速度相同，但是一开始，第一个指针（在指向头结点之前）就落后第二个指针n个结点。接着两者同时移动，当第二个指针移动到为结点时，第一个结点的下一个结点就是我们要删除的结点。
func removeNode(head: ListNode?, _ n: Int) -> ListNode? {
guard let head = head else { return nil } // 链表为空，返回nil
// 创建一个虚拟结点，头结点作为下一个结点
let dummy = ListNode(0)
dummy.next = head
// 前后两个结点指向同一个结点
var previuos: ListNode? = dummy
var current: ListNode? = dummy
// 设置后一个结点的初始位置，即移动n个位置
for _ in 0..<n {
if current == nil { break }
current = current!.next
}
// 同时移动前后两个结点，当后结点指向尾结点循环结束
while current != nil && current!.next != nil {
previuos = previuos!.next
current = current!.next
}
// 删除结点,previuos的下一个结点是待删除的结点
previuos!.next = previuos!.next!.next
return dummy.next
}
