鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)玛瘸，而是在每一個節(jié)點(diǎn)里存到下一個節(jié)點(diǎn)的指針(Pointer)。相對于數(shù)組苟蹈，鏈表具有動態(tài)的大小和靈活的內(nèi)存分配等優(yōu)勢捧韵。

基本概念

鏈表的基本概念如下：

• 節(jié)點(diǎn)（Node）： 鏈表由一個個節(jié)點(diǎn)組成，每個節(jié)點(diǎn)包含兩個部分：數(shù)據(jù)部分（存儲元素的值）和指針部分（指向下一個節(jié)點(diǎn)的指針）汉操。

• 頭節(jié)點(diǎn)（Head Node）： 鏈表的起始節(jié)點(diǎn)稱為頭節(jié)點(diǎn)，它是整個鏈表的入口點(diǎn)蒙兰。

• 尾節(jié)點(diǎn)（Tail Node）： 鏈表的最后一個節(jié)點(diǎn)稱為尾節(jié)點(diǎn)磷瘤，它的指針部分指向空值（NULL）。

常見的鏈表結(jié)構(gòu)

定義一個鏈表節(jié)點(diǎn)類：

import Foundation

/// 定義鏈表節(jié)點(diǎn)類
class ListNode<T> {
    var value: T
    //一般而言搜变，對于雙向鏈表才有prev節(jié)點(diǎn)采缚，這里統(tǒng)一加上
    var prev: ListNode<T>?
    var next: ListNode<T>?
    
    init(value: T) {
        self.value = value
        self.prev = nil
        self.next = nil
    }
}

單向鏈表

單向鏈表（Singly Linked List）：鏈表中最簡單的一種是單向鏈表，它包含兩個域挠他，一個信息域和一個指針域扳抽。

+---+ +---+ +---+ +---+
| 1 | -> | 2 | -> | 3 | -> | 4 |
+---+ +---+ +---+ +---+

在單向鏈表中，每個節(jié)點(diǎn)只有一個指針殖侵，指向下一個節(jié)點(diǎn)贸呢。最后一個節(jié)點(diǎn)的指針指向空值（NULL）。

單鏈表簡單實(shí)現(xiàn)：

/// 單鏈表
class SinglyLinkedList<T> where T: Equatable {
    private var head: ListNode<T>?
    private var tail: ListNode<T>?
    
    func append(value: T) {
        let newNode = ListNode(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
    
    func printList() {
        var currentNode = head
        while let node = currentNode {
            print(node.value)
            currentNode = node.next
        }
    }
    
    func verifyNextOfNode(nodeValue: T, expectedNextValue: T) -> Bool {
        var currentNode = head
        while let node = currentNode {
            if node.value == nodeValue {
                if let nextNode = node.next {
                    return nextNode.value == expectedNextValue
                } else {
                    return false
                }
            }
            currentNode = node.next
        }
        return false
    }
}

// 測試示例
let linkedList = SinglyLinkedList<Int>()
linkedList.append(value: 1)
linkedList.append(value: 2)
linkedList.append(value: 3)
linkedList.printList()
let node1NextIs2 = linkedList.verifyNextOfNode(nodeValue: 1, expectedNextValue: 2)
print("Node 1's next is 2: \(node1NextIs2)")

雙向鏈表

雙向鏈表（Doubly Linked List）：它包含三個域拢军，一個信息域，一個向后的節(jié)點(diǎn)鏈接, 一個向前的節(jié)點(diǎn)鏈接。

+---+    +---+    +---+    +---+

NULL <- | 1 | <-> | 2 | <-> | 3 | <-> | 4 | -> NULL

+---+    +---+    +---+    +---+

在雙向鏈表中景图，每個節(jié)點(diǎn)有兩個指針骗爆，一個指向前一個節(jié)點(diǎn)，一個指向后一個節(jié)點(diǎn)度陆。頭節(jié)點(diǎn)的前指針和尾節(jié)點(diǎn)的后指針指向空值（NULL）艾凯。

雙向鏈表簡單實(shí)現(xiàn)：

/// 雙向鏈表
class DoublyLinkedList<T> where T: Equatable  {
    private var head: ListNode<T>?
    private var tail: ListNode<T>?
    
    func append(value: T) {
        let newNode = ListNode(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
            newNode.prev = tailNode
        } else {
            head = newNode
        }
        tail = newNode
    }
    
    func printList() {
        var currentNode = head
        while let node = currentNode {
            print(node.value)
            currentNode = node.next
        }
    }
    
    func verifyAdjacentNodes(nodeValue: T, expectedPrevValue: T, expectedNextValue: T) -> Bool {
        var currentNode = head
        while let node = currentNode {
            if node.value == nodeValue {
                if let prevNode = node.prev, let nextNode = node.next {
                    return prevNode.value == expectedPrevValue && nextNode.value == expectedNextValue
                } else {
                    return false
                }
            }
            currentNode = node.next
        }
        return false
    }
}

// 測試示例
let dlinkedList = DoublyLinkedList<Int>()
dlinkedList.append(value: 1)
dlinkedList.append(value: 2)
dlinkedList.append(value: 3)
dlinkedList.printList()
let node2PrevIs1NextIs3 = dlinkedList.verifyAdjacentNodes(nodeValue: 2, expectedPrevValue: 1, expectedNextValue: 3)
print("Node 2's next is 3, prev is 1: \(node2PrevIs1NextIs3)")

循環(huán)鏈表

循環(huán)鏈表（Circular Linked List）： 首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起

+---+    +---+    +---+    +---+
| 1 | -> | 2 | -> | 3 | -> | 4 |
+---+    +---+    +---+    +---+
 ^                       |
 |                       v
 +-----------------------+

在循環(huán)鏈表中，最后一個節(jié)點(diǎn)的指針不是指向空值（NULL）懂傀，而是指向頭節(jié)點(diǎn)趾诗，形成一個循環(huán)連接。

循環(huán)鏈表簡單實(shí)現(xiàn)：

/// 循環(huán)列表
class CircularLinkedList<T> {
    private var head: ListNode<T>?
    
    func append(value: T) {
        let newNode = ListNode(value: value)
        if head == nil {
            head = newNode
            newNode.next = newNode
        } else {
            let tail = findTailNode()
            tail.next = newNode
            newNode.next = head
        }
    }
    
    private func findTailNode() -> ListNode<T> {
        var currentNode = head
        while let node = currentNode, node.next !== head {
            currentNode = node.next
        }
        return currentNode!
    }
    
    func printList() {
        var currentNode = head
        while let node = currentNode {
            print(node.value)
            currentNode = node.next
            if currentNode === head {
                break
            }
        }
    }
}

// 測試示例
let clinkedList = CircularLinkedList<Int>()
clinkedList.append(value: 1)
clinkedList.append(value: 2)
clinkedList.append(value: 3)
clinkedList.printList()

數(shù)組與鏈表比較

數(shù)組和鏈表的主要區(qū)別和比較：

這只是對數(shù)組和鏈表的一般比較禁筏，具體應(yīng)用還取決于特定的需求和上下文。有時衡招，可以使用數(shù)組和鏈表的組合來充分發(fā)揮它們的優(yōu)勢篱昔。例如，可以使用數(shù)組來存儲大量數(shù)據(jù)始腾，并使用鏈表來處理插入和刪除操作州刽。

數(shù)組簡單易用，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間浪箭，可以借助 CPU 的緩存機(jī)制穗椅，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高奶栖。而鏈表在內(nèi)存中并不是連續(xù)存儲匹表，所以對 CPU 緩存不友好，沒辦法有效預(yù)讀宣鄙。數(shù)組的缺點(diǎn)是大小固定袍镀，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間。如果聲明的數(shù)組過大框冀，系統(tǒng)可能沒有足夠的連續(xù)內(nèi)存空間分配給它流椒，導(dǎo)致“內(nèi)存不足（out of memory）”。如果聲明的數(shù)組過小明也，則可能出現(xiàn)不夠用的情況宣虾。這時只能再申請一個更大的內(nèi)存空間，把原數(shù)組拷貝進(jìn)去温数，非常費(fèi)時绣硝。鏈表本身沒有大小的限制，支持動態(tài)擴(kuò)容撑刺，這也是它與數(shù)組最大的區(qū)別鹉胖。

鏈表算法題

鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，解決鏈表相關(guān)的算法問題需要掌握鏈表的基本操作和一些常見的思考方法。以下是解決鏈表相關(guān)問題的一般思路：

• 理解問題：
  • 首先甫菠，要充分理解問題陳述挠铲，包括輸入和輸出的要求，以及問題的約束條件寂诱。
• 定義節(jié)點(diǎn)結(jié)構(gòu)：
  • 定義鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)拂苹，通常包括一個值（或數(shù)據(jù)）和一個指向下一個節(jié)點(diǎn)的指針。
• 考慮邊界情況：
  • 確保你考慮了鏈表為空痰洒、只有一個節(jié)點(diǎn)瓢棒、多個節(jié)點(diǎn)等各種可能的情況。
• 基本操作：
  • 掌握鏈表的基本操作丘喻，包括插入節(jié)點(diǎn)脯宿、刪除節(jié)點(diǎn)、反轉(zhuǎn)鏈表泉粉、查找節(jié)點(diǎn)等连霉。這些操作通常需要使用指針來遍歷和操作鏈表。
• 使用快慢指針：
  • 對于某些問題嗡靡，快慢指針技巧非常有用窘面。快慢指針通常用于檢測鏈表中的循環(huán)叽躯、查找中間節(jié)點(diǎn)等。
• 使用遞歸：
  • 一些鏈表問題可以通過遞歸來解決肌括，如遞歸反轉(zhuǎn)鏈表点骑、合并有序鏈表等。遞歸方法可以簡化問題的解決方案谍夭。
• 使用額外的數(shù)據(jù)結(jié)構(gòu)：
  • 在某些情況下黑滴，可以使用額外的數(shù)據(jù)結(jié)構(gòu)（如哈希表）來解決鏈表問題。這可以提高查找效率紧索，但要注意空間復(fù)雜度袁辈。
• 問題分類：
  • 將鏈表問題分類，例如珠漂，分為單鏈表晚缩、雙鏈表、循環(huán)鏈表等媳危，根據(jù)不同類型的鏈表采用不同的解決方法荞彼。
• 思考優(yōu)化：
  • 一旦你有一個解決方案，思考是否有優(yōu)化的空間待笑，如減少遍歷次數(shù)鸣皂、節(jié)省內(nèi)存空間等。
• 寫代碼和測試：
  • 根據(jù)你的思路編寫代碼，并進(jìn)行測試寞缝。確保你的代碼能夠處理各種情況癌压，并且在邊界條件下能夠正確運(yùn)行。
• 時間和空間復(fù)雜度分析：
  • 分析你的算法的時間復(fù)雜度和空間復(fù)雜度荆陆。優(yōu)化算法以減少復(fù)雜度通常是一個好主意滩届。
• 處理異常情況：
  • 考慮處理異常情況，如輸入無效數(shù)據(jù)慎宾、內(nèi)存不足等情況丐吓。
• 優(yōu)化和改進(jìn)：
  • 如果時間允許，可以不斷優(yōu)化你的解決方案趟据，提高性能或減少內(nèi)存占用券犁。

一些常見的鏈表問題包括反轉(zhuǎn)鏈表、合并有序鏈表汹碱、檢測循環(huán)粘衬、查找中間節(jié)點(diǎn)、刪除節(jié)點(diǎn)等咳促。根據(jù)具體的問題稚新，你可以應(yīng)用上述思路和技巧來解決鏈表相關(guān)的算法問題。不斷練習(xí)和挑戰(zhàn)不同類型的問題將有助于提高你的鏈表問題解決能力跪腹。

先定義一個鏈表節(jié)點(diǎn)類和鏈表打印方法褂删，方便后續(xù)測試：

import Foundation

/// 定義鏈表節(jié)點(diǎn)類
class ListNode {
    var value: Int
    var next: ListNode?
    init(value: Int) {
        self.value = value
        self.next = nil
    }
}

/// 打印鏈表
func printLinkedList(_ head: ListNode?) {
    var currentNode: ListNode? = head
    while let node = currentNode {
        //稍微處理下 便于后面測試輸出結(jié)果對比
        if node.next == nil {
            print(node.value,terminator: "\n")
        } else {
            print(node.value,terminator: " ")
        }
        currentNode = node.next
    }
}

鏈表節(jié)點(diǎn)的插入與刪除

當(dāng)在鏈表中插入新節(jié)點(diǎn)時，可以使用兩種常見的策略：頭插法（Head Insertion）和尾插法（Tail Insertion）冲茸。這些策略決定了新節(jié)點(diǎn)在鏈表中的位置屯阀。

• 頭插法（Head Insertion）：在頭插法中，新節(jié)點(diǎn)被插入到鏈表的頭部轴术，成為新的頭節(jié)點(diǎn)难衰。這意味著新節(jié)點(diǎn)的指針將指向原來的頭節(jié)點(diǎn)，而鏈表的頭指針將指向新節(jié)點(diǎn)逗栽。頭插法的時間復(fù)雜度為 O(1)盖袭。

假設(shè)有一個包含四個節(jié)點(diǎn)的鏈表：1 -> 2 -> 3 -> 4。頭插法示意圖：

+---+    +---+    +---+    +---+
| 4 | -> | 3 | -> | 2 | -> | 1 |
+---+    +---+    +---+    +---+

通過頭插法彼宠，新節(jié)點(diǎn)被插入到鏈表的頭部鳄虱。新節(jié)點(diǎn) 4 成為新的頭節(jié)點(diǎn)，其指針指向原來的頭節(jié)點(diǎn) 1凭峡。每個節(jié)點(diǎn)包含一個值和一個指針醇蝴，指針指向下一個節(jié)點(diǎn)。

頭插法常用于需要逆序構(gòu)建鏈表的情況想罕，因?yàn)槊看尾迦氲男鹿?jié)點(diǎn)都會成為新的頭節(jié)點(diǎn)悠栓，鏈表的順序會被顛倒霉涨。

• 尾插法（Tail Insertion）：在尾插法中，新節(jié)點(diǎn)被插入到鏈表的尾部惭适，成為新的尾節(jié)點(diǎn)笙瑟。這意味著新節(jié)點(diǎn)的指針將指向空值（NULL），而原來的尾節(jié)點(diǎn)的指針將指向新節(jié)點(diǎn)癞志。尾插法的時間復(fù)雜度為 O(n)往枷。

尾插法示意圖：

+---+    +---+    +---+    +---+
| 1 | -> | 2 | -> | 3 | -> | 4 |
+---+    +---+    +---+    +---+

通過尾插法，新節(jié)點(diǎn)被插入到鏈表的尾部凄杯。新節(jié)點(diǎn) 4 成為新的尾節(jié)點(diǎn)错洁，原來的尾節(jié)點(diǎn) 3 的指針指向新節(jié)點(diǎn)。每個節(jié)點(diǎn)包含一個值和一個指針戒突，指針指向下一個節(jié)點(diǎn)屯碴。

尾插法常用于保持鏈表的順序不變，每次插入新節(jié)點(diǎn)都在鏈表的尾部進(jìn)行膊存。

頭插法及尾插法代碼實(shí)現(xiàn)：

/// 定義鏈表
class LinkedList {
    var head: ListNode?
    var tail: ListNode?
    
    // 頭插法
    func insertAtHead(_ value: Int) {
        let newNode = ListNode(value:value)
        
        if head == nil {
            head = newNode
            tail = newNode
        } else {
            newNode.next = head
            head = newNode
        }
    }
    
    // 尾插法
    func insertAtTail(_ value: Int) {
        let newNode = ListNode(value:value)
        
        if head == nil {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            tail = newNode
        }
    }
}

// 示例使用
let linkedList = LinkedList()

// 頭插法插入節(jié)點(diǎn)
linkedList.insertAtHead(3)
linkedList.insertAtHead(2)
linkedList.insertAtHead(1)

// 輸出鏈表：1 -> 2 -> 3
printLinkedList(linkedList.head)

// 尾插法插入節(jié)點(diǎn)
linkedList.insertAtTail(4)
linkedList.insertAtTail(5)

// 輸出鏈表：1 -> 2 -> 3 -> 4 -> 5
printLinkedList(linkedList.head)

• 刪除指定節(jié)點(diǎn)：給定要刪除的節(jié)點(diǎn)导而，直接將該節(jié)點(diǎn)從鏈表中移除。這需要修改節(jié)點(diǎn)前一個節(jié)點(diǎn)的 next 指針隔崎，將其指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)今艺，從而跳過要刪除的節(jié)點(diǎn)。

func deleteNode(_ node: ListNode) {
    if let nextNode = node.next {
        node.value = nextNode.value
        node.next = nextNode.next
    } else {
        // 要刪除的節(jié)點(diǎn)是尾節(jié)點(diǎn)爵卒，無法修改前一個節(jié)點(diǎn)的next指針虚缎，所以只能將其置為0
        node.value = 0
    }
}

• 刪除指定值的節(jié)點(diǎn)：給定要刪除的節(jié)點(diǎn)值，在鏈表中查找該值钓株，并刪除對應(yīng)的節(jié)點(diǎn)遥巴。

func deleteNodeWithValue(_ head: ListNode?, value: Int) -> ListNode? {
    let dummy: ListNode = ListNode(value: 0)
    dummy.next = head
    
    var prevNode: ListNode? = dummy
    var currentNode: ListNode? = head
    
    while let node = currentNode {
        if node.value == value {
            prevNode?.next = node.next
            node.next = nil
            break
        }
        
        prevNode = node
        currentNode = node.next
    }
    
    return dummy.next
}

刪除節(jié)點(diǎn)測試代碼：

// 創(chuàng)建一個示例鏈表
let nd1 = ListNode(value: 1)
let nd2 = ListNode(value: 2)
let nd3 = ListNode(value: 3)

nd1.next = nd2
nd2.next = nd3

// 打印原始鏈表
print("Before delete nd2")
// 1 2 3
printLinkedList(nd1)

// 刪除節(jié)點(diǎn)nd2
deleteNode(nd2)

// 刪除指定值為2的節(jié)點(diǎn)
let updateHead = deleteNodeWithValue(nd1, value: 2)
// 1 3
printLinkedList(updateHead)

// 打印刪除節(jié)點(diǎn)后的鏈表
print("After delete nd2")
// 1 3
printLinkedList(nd1)

反轉(zhuǎn)單鏈表

給定一個單鏈表的頭節(jié)點(diǎn)，返回反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)享幽。例如，輸入1->2->3->4->5拾弃，輸出5->4->3->2->1值桩。可以用遞歸或者迭代兩種方式來實(shí)現(xiàn)豪椿。

• 遞歸方式：遞歸的思路是從鏈表的尾部開始反轉(zhuǎn)奔坟，每次將當(dāng)前節(jié)點(diǎn)的next指向前一個節(jié)點(diǎn)，直到到達(dá)頭節(jié)點(diǎn)搭盾。

// 遞歸方式反轉(zhuǎn)單鏈表
func reverseListRecursively(_ head: ListNode?) -> ListNode? {
    // 如果鏈表為空或者只有一個節(jié)點(diǎn)咳秉，則直接返回頭節(jié)點(diǎn)
    if head == nil || head?.next == nil {
        return head
    }
    // 遞歸地反轉(zhuǎn)剩余的鏈表
    let newHead = reverseListRecursively(head?.next)
    // 將當(dāng)前節(jié)點(diǎn)的next指向前一個節(jié)點(diǎn)
    head?.next?.next = head
    // 將當(dāng)前節(jié)點(diǎn)的next置為空
    head?.next = nil
    // 返回新的頭節(jié)點(diǎn)
    return newHead
}

• 迭代方式：迭代的思路是用一個prev指針記錄前一個節(jié)點(diǎn)，一個curr指針記錄當(dāng)前節(jié)點(diǎn)鸯隅，每次將curr的next指向prev澜建，然后更新prev和curr向挖，直到curr為空。

// 迭代方式反轉(zhuǎn)單鏈表
func reverseListIteratively(_ head: ListNode?) -> ListNode? {
    // 初始化前一個節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
    var prev: ListNode? = nil
    var curr: ListNode? = head
    // 遍歷鏈表
    while curr != nil {
        // 記錄當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
        let next = curr?.next
        // 將當(dāng)前節(jié)點(diǎn)的next指向前一個節(jié)點(diǎn)
        curr?.next = prev
        // 更新前一個節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
        prev = curr
        curr = next
    }
    // 返回新的頭節(jié)點(diǎn)炕舵，即原來的尾節(jié)點(diǎn)
    return prev
}

測試示例：

// 創(chuàng)建一個示例鏈表
let node1 = ListNode(value: 1)
let node2 = ListNode(value: 2)
let node3 = ListNode(value: 3)
let node4 = ListNode(value: 4)
let node5 = ListNode(value: 5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

// 打印原始鏈表
print("Before reversing")
printLinkedList(node1)

// 反轉(zhuǎn)鏈表
//let reversedHead = reverseListRecursively(node1)
let reversedHead = reverseListIteratively(node1)

// 打印反轉(zhuǎn)后的鏈表
print("After reversing")
printLinkedList(reversedHead)

//輸出結(jié)果：
/*
Before reversing
1 2 3 4 5
After reversing
5 4 3 2 1
*/

可以看到何之，上述例子遞歸方式和迭代方式都實(shí)現(xiàn)了反轉(zhuǎn)單鏈表的功能。

合并兩個有序鏈表

給定兩個升序排列的單鏈表咽筋，返回合并后的升序排列的單鏈表溶推。例如，輸入1->3->5和2->4->6奸攻，輸出1->2->3->4->5->6蒜危。也可以用遞歸或者迭代兩種方式來實(shí)現(xiàn)。

• 遞歸方式：遞歸的思路是比較兩個鏈表的頭節(jié)點(diǎn)睹耐，選擇較小的那個作為合并后鏈表的頭節(jié)點(diǎn)辐赞，并將其next指向剩余兩個鏈表合并后的結(jié)果。

func mergeTwoListsRecursively(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    // 如果其中一個鏈表為空疏橄，則返回另一個鏈表
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    // 比較兩個鏈表的頭節(jié)點(diǎn)占拍，選擇較小的那個作為合并后鏈表的頭節(jié)點(diǎn)，并將其next指向剩余兩個鏈表合并后的結(jié)果
    if l1!.value < l2!.value {
        l1!.next = mergeTwoListsRecursively(l1!.next, l2)
        return l1
    } else {
        l2!.next = mergeTwoListsRecursively(l1, l2!.next)
        return l2
    }
}

• 迭代方式：迭代的思路是用一個哨兵節(jié)點(diǎn)作為合并后鏈表的虛擬頭節(jié)點(diǎn)捎迫，并用一個指針記錄當(dāng)前位置晃酒，每次比較兩個鏈表的頭節(jié)點(diǎn)，選擇較小的那個接在指針后面窄绒，并更新指針和對應(yīng)的鏈表頭節(jié)點(diǎn)贝次，直到其中一個鏈表為空。

func mergeTwoListsIteratively(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    // 創(chuàng)建一個哨兵節(jié)點(diǎn)作為合并后鏈表的虛擬頭節(jié)點(diǎn)
    let dummy = ListNode(value: 0)
    // 用一個指針記錄當(dāng)前位置
    var curr: ListNode? = dummy
    // 用兩個指針分別遍歷兩個鏈表
    var p1 = l1
    var p2 = l2
    // 當(dāng)兩個鏈表都不為空時彰导，循環(huán)比較它們的頭節(jié)點(diǎn)蛔翅，選擇較小的那個接在curr后面，并更新curr和對應(yīng)的鏈表頭節(jié)點(diǎn)
    while p1 != nil && p2 != nil {
        if p1!.value < p2!.value {
            curr?.next = p1
            p1 = p1?.next
        } else {
            curr?.next = p2
            p2 = p2?.next
        }
        curr = curr?.next
    }
    // 當(dāng)其中一個鏈表為空時位谋，將另一個鏈表的剩余部分接在curr后面
    if p1 == nil {
        curr?.next = p2
    }
    if p2 == nil {
        curr?.next = p1
    }
    // 返回合并后鏈表的真實(shí)頭節(jié)點(diǎn)山析，即哨兵節(jié)點(diǎn)的next
    return dummy.next
}

測試示例：

// 創(chuàng)建兩個示例鏈表
let n1 = ListNode(value: 1)
let n3 = ListNode(value: 3)
let n5 = ListNode(value: 5)
n1.next = n3
n3.next = n5

let n2 = ListNode(value: 2)
let n4 = ListNode(value: 4)
let n6 = ListNode(value: 6)
n2.next = n4
n4.next = n6

print("Before merging")
printLinkedList(n1)
printLinkedList(n2)

let mergedHead = mergeTwoListsRecursively(n1, n2)
//let mergedHead = mergeTwoListsIteratively(n1, n2)

print("After merging")
printLinkedList(mergedHead)

//輸出結(jié)果：
/*
Before merging
1 3 5
2 4 6
After merging
1 2 3 4 5 6
*/

可以看到，上述例子遞歸方式和迭代方式也都實(shí)現(xiàn)了兩個有序鏈表的合并功能掏父。

刪除鏈表中倒數(shù)第n個節(jié)點(diǎn)

給定一個單鏈表和一個整數(shù)n笋轨，返回刪除了倒數(shù)第n個節(jié)點(diǎn)后的鏈表。例如赊淑，輸入1->2->3->4->5和n=2爵政，輸出1->2->3->5。

可以用雙指針法來實(shí)現(xiàn)陶缺。雙指針法的思路是用兩個指針從頭節(jié)點(diǎn)開始遍歷鏈表钾挟，一個快指針先走n步，然后兩個指針同時走饱岸，直到快指針到達(dá)尾節(jié)點(diǎn)掺出，此時慢指針指向的就是倒數(shù)第n+1個節(jié)點(diǎn)徽千，將其next指向下下個節(jié)點(diǎn)即可刪除倒數(shù)第n個節(jié)點(diǎn)。注意要考慮邊界情況蛛砰，比如n大于鏈表長度或者等于鏈表長度時罐栈，需要刪除頭節(jié)點(diǎn)。代碼實(shí)現(xiàn)如下：

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    // 創(chuàng)建一個哨兵節(jié)點(diǎn)作為虛擬頭節(jié)點(diǎn)泥畅，并將其next指向真實(shí)頭節(jié)點(diǎn)
    let dummy = ListNode(value: 0)
    dummy.next = head
    // 初始化快慢指針荠诬，并讓它們都指向哨兵節(jié)點(diǎn)
    var fast: ListNode? = dummy
    var slow: ListNode? = dummy
    // 讓快指針先走n步
    for _ in 0..<n {
        fast = fast?.next
    }
    // 讓快慢指針同時走，直到快指針到達(dá)尾節(jié)點(diǎn)
    while fast?.next != nil {
        fast = fast?.next
        slow = slow?.next
    }
    // 此時慢指針指向的是倒數(shù)第n+1個節(jié)點(diǎn)位仁，將其next指向下下個節(jié)點(diǎn)即可刪除倒數(shù)第n個節(jié)點(diǎn)
    slow?.next = slow?.next?.next
    // 返回真實(shí)頭節(jié)點(diǎn)柑贞，即哨兵節(jié)點(diǎn)的next
    return dummy.next
}

// 創(chuàng)建一個示例鏈表
let no1 = ListNode(value: 1)
let no2 = ListNode(value: 2)
let no3 = ListNode(value: 3)
let no4 = ListNode(value: 4)
let no5 = ListNode(value: 5)

no1.next = no2
no2.next = no3
no3.next = no4
no4.next = no5

print("Before removing")
printLinkedList(no1)

let removed2FromEnd = removeNthFromEnd(no1, 2)

print("After removing")
printLinkedList(removed2FromEnd)

//輸出結(jié)果
/*
Before removing
1 2 3 4 5
After removing
1 2 3 5
*/

在上述代碼中，首先創(chuàng)建了一個啞節(jié)點(diǎn)(dummy)聂抢，將其指向鏈表的頭節(jié)點(diǎn)钧嘶。然后，使用兩個指針fast和 slow琳疏，并將fast指針向前移動n+1次有决。接下來，同時移動fast和slow指針空盼，直到fast指針到達(dá)鏈表末尾书幕。

一旦fast指針到達(dá)末尾，slow指針將指向倒數(shù)第n+1個節(jié)點(diǎn)揽趾√ɑ悖可以通過將slow指針的next指針指向下下個節(jié)點(diǎn)，從而刪除倒數(shù)第n個節(jié)點(diǎn)篱瞎。

最后苟呐，返回啞節(jié)點(diǎn)(dummy)的next指針，即刪除了倒數(shù)第n個節(jié)點(diǎn)后的鏈表俐筋。

判斷鏈表是否有環(huán)

要判斷一個鏈表是否有環(huán)牵素，并返回環(huán)的入口節(jié)點(diǎn)，可以使用快慢指針的方法澄者。示例代碼如下：

func detectCycle(_ head: ListNode?) -> ListNode? {
    var slow: ListNode? = head
    var fast: ListNode? = head
    
    // 判斷鏈表是否有環(huán)
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        
        if slow === fast {
            // 快慢指針相遇笆呆，鏈表有環(huán)
            break
        }
    }
    
    if fast == nil || fast?.next == nil {
        // 鏈表無環(huán)
        return nil
    }
    
    // 找到環(huán)的入口節(jié)點(diǎn)
    slow = head
    while slow !== fast {
        slow = slow?.next
        fast = fast?.next
    }
    
    return slow
}

// 創(chuàng)建一個有環(huán)的示例鏈表
let l1 = ListNode(value: 1)
let l2 = ListNode(value: 2)
let l3 = ListNode(value: 3)
let l4 = ListNode(value: 4)
let l5 = ListNode(value: 5)

l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5
l5.next = l3 // 創(chuàng)建環(huán)，將尾節(jié)點(diǎn)指向l3

// 判斷鏈表是否有環(huán)闷哆，并返回環(huán)的入口節(jié)點(diǎn)
let cycleNode = detectCycle(l1)

if let cycleNode = cycleNode {
    print("鏈表有環(huán)，環(huán)的入口節(jié)點(diǎn)值為: \(cycleNode.value)")
} else {
    print("鏈表無環(huán)")
}

鏈表實(shí)現(xiàn)LRU（Least Recently Used）緩存淘汰算法

鏈表的順序可以表示數(shù)據(jù)項(xiàng)的訪問順序单起，最近訪問的數(shù)據(jù)項(xiàng)位于鏈表的頭部抱怔，最久未訪問的數(shù)據(jù)項(xiàng)位于鏈表的尾部。當(dāng)需要淘汰緩存中的數(shù)據(jù)項(xiàng)時嘀倒，可以選擇鏈表尾部的節(jié)點(diǎn)進(jìn)行刪除屈留。

以下是基于鏈表實(shí)現(xiàn)LRU緩存淘汰算法的示例：

/// 定義LRUCache鏈表節(jié)點(diǎn)類
class LRUCacheNode<Key, Value> {
    var key: Key
    var value: Value
    var next: LRUCacheNode<Key, Value>?
    var prev: LRUCacheNode<Key, Value>?
    
    init(key: Key, value: Value) {
        self.key = key
        self.value = value
        self.next = nil
        self.prev = nil
    }
}

/// 定義LRU緩存類
class LRUCache<Key: Hashable, Value> {
    private let capacity: Int
    private var cache: [Key: LRUCacheNode<Key, Value>]
    private var head: LRUCacheNode<Key, Value>?
    private var tail: LRUCacheNode<Key, Value>?
    
    init(capacity: Int) {
        self.capacity = capacity
        self.cache = [:]
        self.head = nil
        self.tail = nil
    }
    
    /// 獲取緩存中的值
    func get(_ key: Key) -> Value? {
        if let node = cache[key] {
            moveToHead(node)
            return node.value
        }
        return nil
    }
    
    /// 插入或更新緩存中的值
    func put(_ key: Key, _ value: Value) {
        if let node = cache[key] {
            node.value = value
            moveToHead(node)
        } else {
            let newNode = LRUCacheNode(key: key, value: value)
            cache[key] = newNode
            addToHead(newNode)
            
            if cache.count > capacity {
                if let lastNode = tail {
                    removeNode(lastNode)
                    cache[lastNode.key] = nil
                }
            }
        }
    }
    
    /// 將節(jié)點(diǎn)移動到鏈表頭部
    private func moveToHead(_ node: LRUCacheNode<Key, Value>) {
        if node === head {
            return
        }
        
        removeNode(node)
        addToHead(node)
    }
    
    /// 將節(jié)點(diǎn)添加到鏈表頭部
    private func addToHead(_ node: LRUCacheNode<Key, Value>) {
        if head == nil {
            head = node
            tail = node
        } else {
            node.next = head
            head?.prev = node
            head = node
        }
    }
    
    /// 刪除節(jié)點(diǎn)
    private func removeNode(_ node: LRUCacheNode<Key, Value>) {
        if node === head {
            head = node.next
        }
        
        if node === tail {
            tail = node.prev
        }
        
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }
}

在上述示例中局冰，定義了鏈表節(jié)點(diǎn) LRUCacheNode，其中包含鍵（Key）和值（Value）以及指向前一個節(jié)點(diǎn)和后一個節(jié)點(diǎn)的指針灌危。

然后康二，定義了 LRUCache類，用于實(shí)現(xiàn)LRU緩存勇蝙。LRUCache 類包含一個哈希表 cache沫勿，用于快速查找緩存中的節(jié)點(diǎn)。它還包含鏈表的頭節(jié)點(diǎn) head 和尾節(jié)點(diǎn) tail味混，用于維護(hù)節(jié)點(diǎn)的訪問順序产雹。capacity 表示緩存的最大容量。

LRUCache 類中的 get 方法用于獲取緩存中的值翁锡。如果緩存中存在該鍵蔓挖，則將對應(yīng)的節(jié)點(diǎn)移動到鏈表頭部，并返回節(jié)點(diǎn)的值馆衔。

LRUCache 類中的 put 方法用于插入或更新緩存中的值瘟判。如果緩存中已經(jīng)存在該鍵，則更新對應(yīng)節(jié)點(diǎn)的值角溃，并將節(jié)點(diǎn)移動到鏈表頭部拷获。如果緩存中不存在該鍵，則創(chuàng)建一個新節(jié)點(diǎn)开镣，并將其添加到鏈表頭部刀诬。如果緩存超過最大容量，則刪除鏈表尾部的節(jié)點(diǎn)邪财。

LRUCache 類中的私有方法 moveToHead 用于將節(jié)點(diǎn)移動到鏈表頭部陕壹，addToHead 用于將節(jié)點(diǎn)添加到鏈表頭部，removeNode 用于從鏈表中刪除節(jié)點(diǎn)树埠。這些方法用于維護(hù)鏈表的結(jié)構(gòu)和節(jié)點(diǎn)的順序糠馆。

使用示例：

// 創(chuàng)建容量為 3 的 LRUCache
let cache = LRUCache<Int, String>(capacity: 3)

// 插入緩存項(xiàng)
cache.put(1, "Apple")
cache.put(2, "Banana")
cache.put(3, "Cherry")

// 獲取緩存項(xiàng)
print(cache.get(2))  // 輸出: Optional("Banana")

// 緩存項(xiàng)順序: 2 -> 3 -> 1

cache.put(4, "Durian")

// 緩存項(xiàng)順序: 4 -> 2 -> 3

print(cache.get(1))  // 輸出: nil

// 緩存項(xiàng)順序: 4 -> 2 -> 3

cache.put(5, "Elderberry")

// 緩存項(xiàng)順序: 5 -> 4 -> 2

print(cache.get(3))  // 輸出: nil

// 緩存項(xiàng)順序: 5 -> 4 -> 2

在上述示例中，我們創(chuàng)建了一個容量為 3 的 LRUCache 實(shí)例怎憋，并使用 put 方法插入了三個緩存項(xiàng)（鍵值對）又碌。然后，使用 get 方法獲取緩存項(xiàng)的值绊袋。在插入第四個緩存項(xiàng)時毕匀，由于容量已滿，最久未訪問的緩存項(xiàng) 1 被淘汰癌别。最后皂岔，我們再次使用 get 方法獲取緩存項(xiàng)的值，并觀察緩存項(xiàng)的順序展姐。

小結(jié)

解決鏈表相關(guān)的算法問題時躁垛，需要注意以下幾點(diǎn)：

• 鏈表的操作往往需要用到指針或者引用剖毯，因此要注意指針的移動和更新，以及避免指針的丟失和循環(huán)引用教馆。指針和引用的意思都是一樣的逊谋，都是存儲所指對象的內(nèi)存地址。
• 鏈表的操作往往需要用到一些輔助節(jié)點(diǎn)土铺，比如哨兵節(jié)點(diǎn)胶滋，來簡化邊界情況的處理。針對鏈表的插入舒憾、刪除操作镀钓，需要對插入第一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)的情況進(jìn)行特殊處理。
• 鏈表的操作往往可以用遞歸或者迭代兩種方式來實(shí)現(xiàn)镀迂，遞歸的優(yōu)點(diǎn)是代碼簡潔丁溅，缺點(diǎn)是空間復(fù)雜度高，迭代的優(yōu)點(diǎn)是空間復(fù)雜度低探遵，缺點(diǎn)是代碼復(fù)雜窟赏。
• 鏈表的操作往往可以用一些巧妙的方法來優(yōu)化時間復(fù)雜度，比如快慢指針法箱季，哈希表法等涯穷。