二分查找（有序數(shù)組查找目標(biāo)值）

左右游標(biāo)向中間移動(dòng)

func binarySearch(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2 // 避免溢出
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// 測(cè)試
print(binarySearch([1,3,5,7,9], 5)) // 2
print(binarySearch([1,3,5,7,9], 2)) // -1

快速排序（分治思想經(jīng)典排序）

// 主函數(shù)：傳入數(shù)組、左邊界、右邊界
func quickSort(_ nums: inout [Int], _ left: Int, _ right: Int) {
    guard left < right else { return } // 子數(shù)組長(zhǎng)度≤1，直接返回
    let pivotIndex = partition(&nums, left, right) // 分區(qū)，獲取基準(zhǔn)下標(biāo)
    quickSort(&nums, left, pivotIndex - 1) // 遞歸排序左子數(shù)組
    quickSort(&nums, pivotIndex + 1, right) // 遞歸排序右子數(shù)組
}

// 分區(qū)函數(shù)：選最右側(cè)元素為基準(zhǔn)
func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
    let pivot = nums[right] // 基準(zhǔn)值
    var i = left // i 是小于基準(zhǔn)值區(qū)域的右邊界
    
    for j in left..<right { // j 遍歷整個(gè)未分區(qū)區(qū)間
        if nums[j] <= pivot { // 元素≤基準(zhǔn)值，加入左區(qū)域
            nums.swapAt(i, j) // 交換 i 和 j 位置的元素
            i += 1 // 左區(qū)域右邊界右移
        }
    }
    nums.swapAt(i, right) // 將基準(zhǔn)值放到最終位置（i 位置）
    return i // 返回基準(zhǔn)下標(biāo)
}

反轉(zhuǎn)鏈表（鏈表操作高頻題）

通過(guò)三個(gè)指針（prev、curr、nextTemp）逐個(gè)反轉(zhuǎn)節(jié)點(diǎn)指針

• 初始化 prev = nil（前驅(qū)節(jié)點(diǎn)），curr = head（當(dāng)前節(jié)點(diǎn)）；
• 循環(huán)遍歷鏈表：
  保存 curr.next → 防止鏈表斷裂；
  將 curr.next 指向 prev → 反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)指針；
  prev 后移到 curr，curr 后移到 nextTemp；
• 循環(huán)結(jié)束，prev 就是新的頭節(jié)點(diǎn)。

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

func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil // 前驅(qū)節(jié)點(diǎn)初始為 nil
    var curr = head // 當(dāng)前節(jié)點(diǎn)初始為頭節(jié)點(diǎn)
    
    while curr != nil {
        let nextTemp = curr?.next // 保存下一個(gè)節(jié)點(diǎn)，避免丟失
        curr?.next = prev // 反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的指針
        prev = curr // prev 后移
        curr = nextTemp // curr 后移
    }
    return prev // prev 是新的頭節(jié)點(diǎn)
}

二叉樹(shù)的中序遍歷（遞歸 + 迭代兩種寫(xiě)法）

// 二叉樹(shù)節(jié)點(diǎn)定義
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
    }
}

// 寫(xiě)法1：遞歸
func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
}

// 寫(xiě)法2：迭代（棧實(shí)現(xiàn)）
func inorderTraversalIterative(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    var stack = [TreeNode]()
    var curr = root
    
    while curr != nil || !stack.isEmpty {
        // 遍歷左子樹(shù)，全部入棧
        while let node = curr {
            stack.append(node)
            curr = node.left
        }
        let node = stack.removeLast()
        result.append(node.val)
        curr = node.right
    }
    return result
}