夜夜操一区二区,91亚洲人妻精品

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但并不會按線性的順序存儲數(shù)據(jù)，而是在一個節(jié)點(diǎn)里存儲下一個節(jié)點(diǎn)的指針。由于無需順序存儲，鏈表在插入時(shí)復(fù)雜度可以達(dá)到O(1)，比順序表快很多，但是查找一個節(jié)點(diǎn)或訪問特定編號的節(jié)點(diǎn)需O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

與需在內(nèi)存中連續(xù)存儲的線性表（如數(shù)組）相比，鏈表有以下優(yōu)勢：

對鏈表頭節(jié)點(diǎn)進(jìn)行添加、移除操作，所需時(shí)間為常數(shù)。
性能穩(wěn)定。

LinkedListPreview.png

如上圖所示，鏈表是一個節(jié)點(diǎn)鏈。節(jié)點(diǎn)有以下兩個用途：

保存值。
保存下一個節(jié)點(diǎn)的指針。

這篇文章將介紹鏈表的基本特征，手動實(shí)現(xiàn)一個鏈表及其常見操作，并實(shí)現(xiàn) Swift 中的寫時(shí)拷貝（copy-on-write）技術(shù)。最后，還會介紹幾道常見的鏈表算法題。

1. 鏈表分類

LinkedListLinearList.png

線性表（linear list）可以分為順序表和鏈表。

順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。順序表和鏈表有以下幾點(diǎn)區(qū)別：

空間開辟方式：順序表在存儲數(shù)據(jù)之前開辟足夠空間，后期無法改變大?。▌討B(tài)數(shù)組除外），鏈表一次只開辟存儲一個節(jié)點(diǎn)的內(nèi)存空間。一次開辟大量空間比多次開辟小量空間性能好。
空間利用率：鏈表每次申請一個節(jié)點(diǎn)的空間，且位置隨機(jī)。這種申請存儲空間的方式會有很多空間碎片，一定程度上造成了空間浪費(fèi)。此外，鏈表每個節(jié)點(diǎn)至少需攜帶一個指針，增加了空間占用。因此，順序表空間利用率比鏈表高。
時(shí)間復(fù)雜度：順序表可以使用下標(biāo)直接訪問元素，它的時(shí)間復(fù)雜度為O(1)，鏈表需從頭開始，依次遍歷，時(shí)間復(fù)雜度為O(n)。順序表中插入、刪除、移動元素，可能涉及大量元素的整體移動，時(shí)間復(fù)雜度為O(n)，鏈表插入、刪除、移動元素，只需改變指針指向，時(shí)間復(fù)雜度為O(1)。

鏈表可以分為以下幾類：

單向鏈表（singly linked list）：是鏈表中最簡單的，它包含兩個域，一個信息域和一個指針域，指針指向鏈表中的下一個節(jié)點(diǎn)，最后一個節(jié)點(diǎn)的指針指向一個空值。

LinkedListSingly.png

靜態(tài)單向鏈表：用數(shù)組描述的單向鏈表，稱為靜態(tài)單向鏈表。它的內(nèi)存地址是連續(xù)的，需預(yù)先分配大小。
動態(tài)單向鏈表：用申請內(nèi)存的函數(shù)動態(tài)申請內(nèi)存，鏈表長度沒有限制，節(jié)點(diǎn)內(nèi)存地址不是連續(xù)的，需通過指針來順序訪問。
雙向鏈表（doubly linked list）：每個節(jié)點(diǎn)有兩個連接，一個指向前一節(jié)點(diǎn)，另一個指向后一節(jié)點(diǎn)。首、尾節(jié)點(diǎn)對應(yīng)的前、后連接指向空值或空列表。

LinkedListDoubly.png

循環(huán)鏈表（circular linked list）：首節(jié)點(diǎn)、尾節(jié)點(diǎn)連接在一起。循環(huán)鏈表第一個節(jié)點(diǎn)之前就是最后一個節(jié)點(diǎn)；反之亦然。

LinkedListCircularly.png

單向循環(huán)鏈表：它的最后一個節(jié)點(diǎn)指針不是 NULL，而改為指向頭節(jié)點(diǎn)，從而整個鏈表形成一個環(huán)。
雙向循環(huán)鏈表：由單向循環(huán)鏈表可以推斷出雙向循環(huán)鏈表，它的頭節(jié)點(diǎn)還會指向尾節(jié)點(diǎn)。

這篇文章只介紹單向鏈表。

2. 節(jié)點(diǎn) Node

創(chuàng)建 Node.swift 文件，添加以下代碼：

public class Node<Value> {
    public var value: Value
    public var next: Node?
    
    public 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) + " "
    }
}

在 playground page 添加以下代碼：

example(of: "creating and linking nodes") {
    let node1 = Node(value: 1)
    let node2 = Node(value: 2)
    let node3 = Node(value: 3)
    
    node1.next = node2
    node2.next = node3
    
    print(node1)
}

上述代碼創(chuàng)建了三個 node，并鏈接起來。

LinkedListChain.png

控制臺輸出如下：

--- Example of creating and linking nodes ---
1 -> 2 -> 3

使用上述方式創(chuàng)建鏈表會很麻煩，后續(xù)會通過 LinkedList 管理 node。

3. 創(chuàng)建鏈表 LinkedList

創(chuàng)建 LinkedList.swift 文件，并添加以下代碼：

public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?
    
    public init() { }
    
    public var isEmpty: Bool {
        head == nil
    }
}

extension LinkedList: CustomStringConvertible {
    public var description: String {
        guard let head = head else { return "Empty list" }
        return String(describing: head)
    }
}

Linked list 有頭、尾概念，指向鏈表的第一個和最后一個節(jié)點(diǎn)。

LinkedListHeadTail.png

4. 向鏈表添加節(jié)點(diǎn)

后續(xù)會逐步為鏈表提供管理 node 的接口。先提供添加節(jié)點(diǎn)的功能。有以下三種添加節(jié)點(diǎn)的方式：

push：向鏈表頭部添加節(jié)點(diǎn)。
append：向鏈表尾部添加節(jié)點(diǎn)。
insert(after:)：向指定節(jié)點(diǎn)后添加節(jié)點(diǎn)。

下面會依次實(shí)現(xiàn)上述接口，并分析其性能。

4.1 push 操作

向鏈表頭部添加節(jié)點(diǎn)被稱為 push 操作。它的實(shí)現(xiàn)非常簡單：

    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }

當(dāng)向空鏈表 push 時(shí)，新添加的 node 既是 head，也是 tail。

在 playground page 添加以下代碼：

example(of: "push") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print(list)
}

控制臺輸出如下：

--- Example of push ---
1 -> 2 -> 3

4.2 append 操作

append 是向鏈表尾部添加節(jié)點(diǎn)。

在 LinkedList.swift 文件的push(value:)方法下面添加以下代碼：

    public mutating func append(_ value: Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        tail!.next = Node(value: value)
        tail = tail!.next
    }

當(dāng)鏈表為空時(shí)，直接使用 push 添加，這樣可以自動處理 head、tail；不為空時(shí)，在尾部添加一個 node，并將其設(shè)置為 tail。

在 playground page 添加以下代碼：

example(of: "append") {
    var list = LinkedList<Int>()
    list.append(1)
    list.append(2)
    list.append(3)
    
    print(list)
}

輸出如下：

--- Example of append ---
1 -> 2 -> 3

4.3 insert(after:) 操作

insert(after:)向指定位置插入 node，它需要兩步操作：

查找到指定 node。
插入 node。

首先，實(shí)現(xiàn)查找指定 index 位置 node：

    public func node(at index: Int) -> Node<Value>? {
        var currentNode = head
        var currentIndex = 0
        
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode!.next
            currentIndex += 1
        }
        
        return currentNode
    }

node(at:)函數(shù)根據(jù) index 提取 node。由于單向鏈表只能從 head 開始查找，必須迭代遍歷鏈表。

其次，插入 node：

    @discardableResult
    public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
        guard tail !== node else {
            append(value)
            return tail!
        }
        
        node.next = Node(value: value, next: node.next)
        return node.next!
    }

當(dāng)要插入的 node 是 tail 時(shí)，直接調(diào)用 append；否則，將新節(jié)點(diǎn)插入到指定位置。

在 playground page 添加以下代碼：

example(of: "inserting at a particular index") {
    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)")
}

控制臺輸出如下：

--- Example of inserting at a particular index ---
Before inserting: 1 -> 2 -> 3  
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3

4.4 時(shí)間復(fù)雜度

目前，已經(jīng)實(shí)現(xiàn)了三種添加 node、一種查找指定 index 的 node 方法。下面是其時(shí)間復(fù)雜度：

	push(value:)	append(value:)	insert(after:)	node(at:)
用途	向頭部添加	向尾部拼接	向指定 node 后添加	返回指定index處node
時(shí)間復(fù)雜度	O(1)	O(1)	O(1)	O(n)，n 是 index。

5. 移除鏈表的節(jié)點(diǎn)

移除鏈表節(jié)點(diǎn)主要有以下三種操作：

pop：移除頭部節(jié)點(diǎn)。
removeLast：移除尾部節(jié)點(diǎn)。
remove(at:)：移除任意位置節(jié)點(diǎn)。

5.1 pop 操作

移除頭部節(jié)點(diǎn)常稱為 pop。pop 與 push 一樣簡單。

在 LinkedList 添加以下代碼：

    @discardableResult
    public mutating func pop() -> Value? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

pop 會返回被移除的節(jié)點(diǎn)。由于鏈表可能是空的，返回值為可選類型。通過將 head 向后移動一步，可以將 head 移除。方法執(zhí)行完畢后，ARC 會自動將原來 head 占用的內(nèi)存釋放掉。如果移除后鏈表變?yōu)榭樟?，則 tail 設(shè)置為 nil。

在 playground page 添加以下代碼：

example(of: "pop") {
    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))
}

控制臺輸出如下：

--- Example of pop ---
Before popping list: 1 -> 2 -> 3  
After popping list: 2 -> 3 
Popped value: Optional(1)

5.2 removeLast 操作

雖然有指向 tail 的指針，但單向鏈表只能從 head 向 tail 方向查找，后一個節(jié)點(diǎn)并沒有指向上一個節(jié)點(diǎn)的指針。因此，必須遍歷整個鏈表。

在 LinkedList.swift 添加以下代碼：

    @discardableResult
    public mutating func removeLast() -> Value? {
        // 如果 head 是nil，則沒有可供移除的，直接返回nil。
        guard let head = head else { return nil }
        
        // 如果鏈表只有一個節(jié)點(diǎn)，則removeLast等于pop。pop會自動更新head、tail
        guard head.next != nil else {
            return pop()
        }
        
        // 查找current.next，直到為nil。即current為最后一個。
        var prev = head
        var current = head
        while let next = current.next {
            prev = current
            current = next
        }
        
        // current 是最后一個node，使用 prev 斷開鏈表，更新 tail。
        prev.next = nil
        tail = prev
        return current.value
    }

打開 playground page，添加以下代碼：

example(of: "removing the last node") {
    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 last node: \(list)")
    print("Removed value: " + String(describing: removedValue))
}

控制臺輸出如下：

--- Example of removing the last node ---
Before removing last node: 1 -> 2 -> 3  
After removing last node: 1 -> 2 
Removed value: Optional(3)

移除最后一個節(jié)點(diǎn)需遍歷整個鏈表，它的時(shí)間復(fù)雜度為O(n)。

5.3 remove(after:) 操作

remove(after:)與insert(after:)有些相似，都是先找到指定 node，再進(jìn)行操作。

LinkedListRemoveAfter.png

在 LinkedList.swift 文件添加以下代碼：

    @discardableResult
    public mutating func remove(after node: Node<Value>) -> Value? {
        defer { // unlinking 操作在 defer 里執(zhí)行。
            if node.next === tail { // 如果 node.next 是 tail，更新 tail。
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }

打開 playground page，添加以下代碼：

example(of: "removing a node after a particular 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))
}

控制臺輸出如下：

--- Example of removing a node after a particular node ---
Before removing at particular index: 1 -> 2 -> 3  
After removing at index 1: 1 -> 3 
Removed value: Optional(2)

remove(after:)操作時(shí)間復(fù)雜度是O(1)，與insert(after:)類似。

5.4 時(shí)間復(fù)雜度

目前，已經(jīng)實(shí)現(xiàn)了三種移除 node 的方法。下面是其時(shí)間復(fù)雜度：

	pop()	removeLast()	remove(after:)
用途	移除頭部節(jié)點(diǎn)	移除尾部節(jié)點(diǎn)	移除指定節(jié)點(diǎn)后節(jié)點(diǎn)
時(shí)間復(fù)雜度	O(1)	O(n)	O(1)

6 值語義和寫時(shí)拷貝

在 Swift 中，值類型存放在棧區(qū)，引用類型存放在堆區(qū)，但有些值類型（如字符串、數(shù)組），會間接將值保存在堆中，因此，它們是由引用類型支持的值類型。

Swift 中，值類型的拷貝是深拷貝（deep copy），值語義（value semantics）的新對象和原對象是獨(dú)立的，當(dāng)改變新對象的屬性，原對象不受影響；反之同理。

引用類型的賦值是淺拷貝（shallow copy），引用語義（reference semantics）的新對象和原對象變量名雖然不同，但其引用是相同的，即指向相同的內(nèi)存空間。因此，當(dāng)操作新對象內(nèi)部數(shù)據(jù)時(shí)，原對象的內(nèi)部數(shù)據(jù)也會同步更新，其本質(zhì)上是兩個指針指向同一份數(shù)據(jù)。

Swift 中的集合是值語義（value semantics），通過寫時(shí)拷貝（copy-on-write，簡稱為 COW）技術(shù)實(shí)現(xiàn)。

在 playground page 添加以下代碼：

example(of: "array cow") {
    let array1 = [1, 2]
    var array2 = array1
    
    print("array1: \(array1)")
    print("array2: \(array2)")
    
    print("--- After adding 3 to array 2 ---")
    array2.append(3)
    print("array1: \(array1)")
    print("array2: \(array2)")
}

執(zhí)行后輸出如下：

--- Example of array cow ---
array1: [1, 2]
array2: [1, 2]
--- After adding 3 to array 2 ---
array1: [1, 2]
array2: [1, 2, 3]

當(dāng)向 array2 添加元素時(shí)，array1 的元素并未發(fā)生變化。這是因?yàn)?array2 調(diào)用 append 時(shí)復(fù)制了一份 array1 的數(shù)據(jù)。

LinkedListCOW.png

那之前創(chuàng)建的 LinkedList 是否是值語義呢？在 playground page 添加以下代碼：

example(of: "linked list cow") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
    var list2 = list1
    print("List1: \(list1)")
    print("List2: \(list2)")
    
    print("After appending 3 to list2")
    list2.append(3)
    print("List1: \(list1)")
    print("List2: \(list2)")
}

執(zhí)行后控制臺輸出如下：

--- Example of linked list cow ---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2
List1: 1 -> 2 -> 3  
List2: 1 -> 2 -> 3

可見 LinkedList 不是值語義，這是因?yàn)殒湵淼讓哟鎯κ褂昧艘妙愋汀inkedList 是結(jié)構(gòu)體，應(yīng)使用值語義，但目前卻是引用語義，使用 COW 可以解決這一問題。

使用 COW 實(shí)現(xiàn)值語義的策略很簡單，就是在改變鏈表內(nèi)容前，將鏈表的存儲復(fù)制一份，并更新 head、tail。

在 LinkedList.swift 文件中添加以下代碼：

    private mutating func copyNodes() {
        guard var oldNode = head else {
            return
        }
        
        head = Node(value: oldNode.value)
        var newNode = head
        
        while let nextOldNode = oldNode.next {
            newNode!.next = Node(value: nextOldNode.value)
            newNode = newNode!.next
            
            oldNode = nextOldNode
        }
        
        tail = newNode
    }

copyNodes()方法會使用新初始化的 node 替換原來 node，組建鏈表。

為 LinkedList 中使用了 mutating 關(guān)鍵字的方法添加copyNodes()調(diào)用。共以下六個方法：

push
append
insert(after:)
pop
removeLast
remove(after:)

更新后其會變成值語義，再次執(zhí)行控制臺輸出如下：

--- Example of linked list cow ---
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2
List1: 1 -> 2 
List2: 1 -> 2 -> 3

但每次調(diào)用copyNodes()都會產(chǎn)生O(n)時(shí)間復(fù)雜度的開銷，下面會提供進(jìn)一步的優(yōu)化方案。

7. 優(yōu)化 COW

有兩種方案解決每個 mutating 都會產(chǎn)生O(n)開銷的問題：

只有當(dāng)大于一個指針指向鏈表時(shí)，才進(jìn)行復(fù)制。
共用部分 node，只復(fù)制不同部分。

7.1 isKnownUniquelyReferenced

Swift 中的isKnownUniquelyReferenced可以查看對象是否只引用了一次，更新復(fù)制 LinkedList 代碼如下：

example(of: "linked list cow") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
//    var list2 = list1
    
    // 使用isKnownUniquelyReferenced更新
    print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")
    var list2 = list1
    print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")
    
    print("List1: \(list1)")
    print("List2: \(list2)")
    
    print("After appending 3 to list2")
    list2.append(3)
    print("List1: \(list1)")
    print("List2: \(list2)")
}

執(zhí)行后控制臺輸出如下：

List1 uniquely referenced: true
List1 uniquely referenced: false

isKnownUniquelyReferenced可以查看對象是否只引用了一次，在copyNode()方法開始位置添加以下代碼：

        // 如果只引用了一次，不要進(jìn)行復(fù)制，
        guard !isKnownUniquelyReferenced(&head) else {
            return
        }

更新后，只有存在多個引用時(shí)，才會進(jìn)行復(fù)制。

7.2 共享節(jié)點(diǎn)

第二種優(yōu)化方案是共享節(jié)點(diǎn)，并不是有多個引用就一定需要復(fù)制，共享節(jié)點(diǎn)在一定程度上可以避免復(fù)制。

請看下面的示例：

    var list1 = LinkedList<Int>()
    (1...3).forEach({ list1.append($0) })
    var list2 = list1

LinkedListSharingNodes.png

禁用 cow 后執(zhí)行以下操作：

    list2.push(0)

LinkedListSharingNodesPush.png

list2 的 push 操作并不會影響 list1，打印 list1、list2：

--- Example of sharing nodes ---
List1: 1 -> 2 -> 3  
List2: 0 -> 1 -> 2 -> 3

list1 push 操作也不會影響 list2：

    list1.push(100)

LinkedListSharingNodesPush2.png

單向鏈表頭部插入可以避免 COW 的開銷。

7.3 開啟 COW 時(shí)移除節(jié)點(diǎn)會產(chǎn)生錯誤

使用以下代碼，查看開啟 cow 后移除節(jié)點(diǎn)：

example(of: "cow remove") {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
    list1.append(3)
    var list2 = list1
    
    if let node = list2.node(at: 0) {
        list2.remove(after: node)
    }
    print("List1: \(list1)")
    print("List2: \(list2)"）
}

執(zhí)行后控制臺輸出如下：

--- Example of cow remove ---
List1: 1 -> 3 
List2: 1 -> 2 -> 3

可以看到 remove 操作從錯誤的鏈表移除了對象。這是因?yàn)槊總€ mutating 操作都會觸發(fā)復(fù)制，remove(after:)移除的是復(fù)制前的鏈表。

下面增加一個返回復(fù)制后節(jié)點(diǎn)方法：

    /// 返回復(fù)制后的node，用于移除操作。
    private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {
        guard !isKnownUniquelyReferenced(&head) else {
            return nil
        }
        guard var oldNode = head else {
            return nil
        }
        
        head = Node(value: oldNode.value)
        var newNode = head
        var nodeCopy: Node<Value>?
        
        while let nextOldNode = oldNode.next {
            if oldNode === node {
                nodeCopy = newNode
            }
            
            newNode!.next = Node(value: nextOldNode.value)
            newNode = newNode!.next
            oldNode = nextOldNode
        }
        
        return nodeCopy
    }

copyNode(node:)與之前的copyNode()有很多相似之處，只是它返回復(fù)制后的 node。更新remve(after:)如下：

    @discardableResult
    public mutating func remove(after node: Node<Value>) -> Value? {
        // 開啟 cow 后，使用復(fù)制后的node移除不會產(chǎn)生問題。
        guard let node = copyNodes(returningCopyOf: node) else { return nil}
        
        defer { // unlinking 操作在 defer 里執(zhí)行。
            if node.next === tail { // 如果 node.next 是 tail，更新 tail。
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }

目前，移除操作工作正常。

8. 鏈表相關(guān)算法題

這一部分介紹五道鏈表算法題。

8.1 逆序打印鏈表節(jié)點(diǎn)

輸入一個鏈表，從尾到頭反歸來打印每個節(jié)點(diǎn)的值：

輸入：1->2->3->NULL
打印：3->2->1->NULL

使用遞歸可以很好解決逆序打印問題。遞歸可以構(gòu)建調(diào)用堆棧，只需在調(diào)用堆棧展開時(shí)調(diào)用 print 語句即可。

代碼如下：

func printInReverse<T>(_ list: LinkedList<T>) {
    printInReverse(list.head)
}

private func printInReverse<T>(_ node: Node<T>?) {
    // node 為nil時(shí)，已經(jīng)遞歸到了 tail。
    guard let node = node else { return }
    
    print("Before")
    
    // 通過遞歸構(gòu)建調(diào)用堆棧，
    printInReverse(node.next)
    
    // 只有遞歸結(jié)束后，才會執(zhí)行下面輸出。
    print("After")
    print(node.value)
}

example(of: "printing in reverse") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("original list: \(list)")
    print("Printing in reverse:")
    printInReverse(list)
}

輸出如下：

--- Example of printing in reverse ---
original list: 1 -> 2 -> 3  
Printing in reverse:
Before
Before
Before
After
3
After
2
After
1

上述方法需遍歷每個 node，因此它的時(shí)間復(fù)雜度為O(n)。因?yàn)殡[式地使用了函數(shù)調(diào)用堆棧來處理 node，它的空間復(fù)雜度同樣為O(n)。

8.2 查找鏈表的中間節(jié)點(diǎn)

給定一個鏈表，返回鏈表的中間節(jié)點(diǎn)：

輸入：1->2->3->NULL
輸出：2->3->NULL

鏈表的缺點(diǎn)在于不能通過下標(biāo)訪問對應(yīng)的元素，因此可以考慮使用兩個指針slow與fast一起遍歷鏈表。slow一次走一步，fast一次走兩步。那么當(dāng)fast到達(dá)鏈表的末尾時(shí)，slow必然位于中間。

func getMiddle<T>(_ list: LinkedList<T>) -> Node<T>? {
    var slow = list.head
    var fast = list.head
    
    // fast 遍歷速度是 slow 的二倍，fast 到達(dá)終點(diǎn)時(shí)，slow 剛好處于中間。
    while let nextFast = fast?.next {
        fast = nextFast.next
        slow = slow?.next
    }
    
    return slow
}

example(of: "getting the middle node") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(1)
    
    print(list)
    
    if let middleNode = getMiddle(list) {
        print(middleNode)
    }
}

因?yàn)樾枰闅v鏈表，它的時(shí)間復(fù)雜度為O(n)。遍歷的過程中只需常數(shù)空間存放slow、fast兩個指針，它的空間復(fù)雜度為O(1)。

8.3 反轉(zhuǎn)鏈表

反轉(zhuǎn)一個單向鏈表。如下所示：

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個元素。由于節(jié)點(diǎn)沒有存儲其上一個節(jié)點(diǎn)，因此必須事先存儲其前一個元素。在更改引用前，還需另一個指針來存儲下一個節(jié)點(diǎn)。最后，返回新的頭引用。

extension LinkedList {
    mutating func reverse() {
        // 通過操控 node 的 next，避免創(chuàng)建額外的 node、LinkedList。
        tail = head
        var prev = head
        var current = head?.next
        prev?.next = nil
        
        while current != nil {  // 每次循環(huán)時(shí)，創(chuàng)建一個新的引用指向下一個節(jié)點(diǎn)。循環(huán)過程中，讓每個節(jié)點(diǎn)指向上一個節(jié)點(diǎn)。
            let next = current?.next
            current?.next = prev
            prev = current
            current = next
        }
        
        // 循環(huán)結(jié)束時(shí)，設(shè)置 head 為 prev。
        head = prev
    }
}

example(of: "reversing a list") {
    var list = LinkedList<Int>()
    list.push(5)
    list.push(4)
    list.push(3)
    list.push(2)
    list.push(1)
    
    print("Original list: \(list)")
    list.reverse()
    print("Reversed list: \(list)")
}

因?yàn)橐h(huán)整個鏈表，它的時(shí)間復(fù)雜度是O(n)。整個過程無需初始化新的鏈表、節(jié)點(diǎn)，它的空間復(fù)雜度是O(1)。

8.4 合并兩個有序鏈表

將兩個升序鏈表合并為一個新的升序鏈表并返回。如下所示：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

可以用迭代的方法實(shí)現(xiàn)上述算法。當(dāng)兩個鏈表都不是空鏈表時(shí)，比較哪個鏈表的頭節(jié)點(diǎn)值更小，將較小值的節(jié)點(diǎn)添加到結(jié)果里，并將該鏈表中的節(jié)點(diǎn)向后移動一位。

循環(huán)終止時(shí)，至多一個鏈表是非空的。由于，輸入的兩個鏈表都是有序的，不管哪個鏈表非空，它都比前面已經(jīng)合并鏈表的末尾值大，意味著此時(shí)可以直接將非空鏈表接到合并鏈表后面，最后返回合并的鏈表即可。

func mergeSorted<T: Comparable>(_ left: LinkedList<T>, _ right: LinkedList<T>) -> LinkedList<T> {
    // 如果一個鏈表為空，則直接返回另一個鏈表
    guard !left.isEmpty else {
        return right
    }
    guard !right.isEmpty else {
        return left
    }
    
    var newHead: Node<T>?
    var tail: Node<T>?
    var currentLeft = left.head
    var currentRight = right.head
    
    if let leftNode = currentLeft, let rightNode = currentRight {
        if leftNode.value < rightNode.value {
            newHead = leftNode
            currentLeft = leftNode.next
        } else {
            newHead = rightNode
            currentRight = rightNode.next
        }
        
        tail = newHead
    }
    
    while let leftNode = currentLeft, let rightNode = currentRight {    // 循環(huán)會持續(xù)到任意鏈表為空
        // 比較值
        if leftNode.value < rightNode.value {
            tail?.next = leftNode
            currentLeft = leftNode.next
        } else {
            tail?.next = rightNode
            currentRight = rightNode.next
        }
        
        tail = tail?.next
    }
    
    // 把剩余鏈表拼接上去
    if let leftNodes = currentLeft {
        tail?.next = leftNodes
    }
    if let rightNodes = currentRight {
        tail?.next = rightNodes
    }
    
    // 創(chuàng)建新的鏈表，設(shè)置head、tail。
    var list = LinkedList<T>()
    list.head = newHead
    list.tail = {
        while let next = tail?.next {
            tail = next
        }
        return tail
    }()
    return list
}

example(of: "merging two lists") {
    var list = LinkedList<Int>()
    list.push(5)
    list.push(4)
    list.push(1)
    
    var anotherList = LinkedList<Int>()
    anotherList.push(6)
    anotherList.push(3)
    anotherList.push(2)
    anotherList.push(1)
    
    print("First list: \(list)")
    print("Second list: \(anotherList)")
    
    let mergedList = mergeSorted(list, anotherList)
    print("Merged list: \(mergedList)")
}

上述算法的時(shí)間復(fù)雜度為O(n+m)，其中，n和m分別為兩個鏈表的長度。每次循環(huán)迭代中，只有一個鏈表的元素會被放入合并鏈表中，因此while循環(huán)次數(shù)不會超過兩個鏈表的長度之和。整個過程只需常數(shù)空間存放若干變量，因此，它的空間復(fù)雜度是O(1)。

8.5 刪除鏈表中等于給定值的所有節(jié)點(diǎn)

刪除鏈表中等于給定值的所有節(jié)點(diǎn)，示例：

輸入: 6->2->6->3->4->5->6, val = 6
輸出: 2->3->4->5

如果刪除的節(jié)點(diǎn)是中間節(jié)點(diǎn)，則非常簡單：

選擇要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) prev。
將 prev 的 next 設(shè)置為要刪除的 next。

LinkedListRemoveMiddle.png

當(dāng)要刪除的一個或多個節(jié)點(diǎn)位于鏈表頭部時(shí)，可以先遍歷鏈表，看其頭部是否與指定值相等。如果相等，則設(shè)置其頭部指向下一個節(jié)點(diǎn)。

LinkedListRemoveHead.png

如下所示：

extension LinkedList where Value: Equatable {
    mutating func removeAll(_ value: Value) {
        // 先處理 head 的值與指定值相同
        while let head = self.head, head.value == value {
            self.head = head.next
        }
        
        var prev = head
        var current = head?.next
        while let currentNode = current {
            guard currentNode.value != value else { // 如果節(jié)點(diǎn)值與要移除值相等，移動指針。
                prev?.next = currentNode.next
                current = prev?.next
                continue
            }
            
            prev = current
            current = current?.next
        }
        
        // tail 可能被移除
        tail = prev
    }
}

example(of: "deleting duplicate nodes") {
    var list = LinkedList<Int>()
    list.push(3)
    list.push(2)
    list.push(2)
    list.push(1)
    list.push(1)
    
    list.removeAll(2)
    print(list)
}

因?yàn)樾枰闅v每一個元素，它的時(shí)間復(fù)雜度是O(n)。只需常數(shù)空間存放若干變量，因此空間復(fù)雜度是O(1)。

總結(jié)

使用鏈表可以克服數(shù)組需預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)內(nèi)存動態(tài)管理，但鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)。此外，鏈表增加了節(jié)點(diǎn)的指針域，空間開銷比較大。

Demo名稱：LinkedList
源碼地址：https://github.com/pro648/BasicDemos-iOS/tree/master/LinkedList

參考資料：

鏈表
Linked Lists

歡迎更多指正：https://github.com/pro648/tips

本文地址：https://github.com/pro648/tips/blob/master/sources/鏈表%20LinkedList.md

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

鏈表 LinkedList

鏈表 LinkedList

1. 鏈表分類

2. 節(jié)點(diǎn) Node

3. 創(chuàng)建鏈表 LinkedList

4. 向鏈表添加節(jié)點(diǎn)

4.1 push 操作

4.2 append 操作

4.3 insert(after:) 操作

4.4 時(shí)間復(fù)雜度

5. 移除鏈表的節(jié)點(diǎn)

5.1 pop 操作

5.2 removeLast 操作

5.3 remove(after:) 操作

5.4 時(shí)間復(fù)雜度

6 值語義和寫時(shí)拷貝

7. 優(yōu)化 COW

7.1 isKnownUniquelyReferenced

7.2 共享節(jié)點(diǎn)

7.3 開啟 COW 時(shí)移除節(jié)點(diǎn)會產(chǎn)生錯誤

8. 鏈表相關(guān)算法題

8.1 逆序打印鏈表節(jié)點(diǎn)

8.2 查找鏈表的中間節(jié)點(diǎn)

8.3 反轉(zhuǎn)鏈表

8.4 合并兩個有序鏈表

8.5 刪除鏈表中等于給定值的所有節(jié)點(diǎn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

鏈表 LinkedList

1. 鏈表分類

2. 節(jié)點(diǎn) Node

3. 創(chuàng)建鏈表 LinkedList

4. 向鏈表添加節(jié)點(diǎn)

4.1 push 操作

4.2 append 操作

4.3 insert(after:) 操作

4.4 時(shí)間復(fù)雜度

5. 移除鏈表的節(jié)點(diǎn)

5.1 pop 操作

5.2 removeLast 操作

5.3 remove(after:) 操作

5.4 時(shí)間復(fù)雜度

6 值語義和寫時(shí)拷貝

7. 優(yōu)化 COW

7.1 isKnownUniquelyReferenced

7.2 共享節(jié)點(diǎn)

7.3 開啟 COW 時(shí)移除節(jié)點(diǎn)會產(chǎn)生錯誤

8. 鏈表相關(guān)算法題

8.1 逆序打印鏈表節(jié)點(diǎn)

8.2 查找鏈表的中間節(jié)點(diǎn)

8.3 反轉(zhuǎn)鏈表

8.4 合并兩個有序鏈表

8.5 刪除鏈表中等于給定值的所有節(jié)點(diǎn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av