Swift - 链表的使用

基本知识点

节点（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
    }