数组链表练习

欢迎大家来到IT世界,在知识的湖畔探索吧!

数组链表练习

1) 数组（Array）

1.1 一个支持动态扩容的数组实现

思路：用“容量(capacity) ×2 扩容、≤1/4 缩容”的策略实现 append/insert/remove。
Swift 版本用
[T?] 自管容量；Python 版本用 ctypes.py_object 实现“真·底层数组”。

Swift

/// 一个简易的动态数组（演示扩容/缩容策略） /// - 策略：满容时容量×2；元素个数 <= 容量/4 时缩容为 1/2（最小为1） /// - 复杂度： /// - 追加/尾删：摊还 O(1) /// - 按下标插入/删除：O(n)（需要搬移） /// - 下标访问：O(1) final class DynamicArray<T> { private var storage: [T?] private(set) var count: Int = 0 private(set) var capacity: Int init(initialCapacity: Int = 4) { self.capacity = max(1, initialCapacity) self.storage = Array<T?>(repeating: nil, count: capacity) } private func resize(to newCapacity: Int) { var newStore = Array<T?>(repeating: nil, count: newCapacity) for i in 0..<count { newStore[i] = storage[i] } storage = newStore capacity = newCapacity } func append(_ value: T) { if count == capacity { resize(to: capacity * 2) } storage[count] = value count += 1 } func insert(_ value: T, at index: Int) { precondition(index >= 0 && index <= count, "index out of range") if count == capacity { resize(to: capacity * 2) } // 右移 [index, count-1] for i in stride(from: count, to: index, by: -1) { storage[i] = storage[i - 1] } storage[index] = value count += 1 } @discardableResult func removeLast() -> T { precondition(count > 0, "empty") let val = storage[count - 1]! storage[count - 1] = nil count -= 1 if count > 0 && count <= capacity / 4 { resize(to: max(1, capacity / 2)) } return val } @discardableResult func remove(at index: Int) -> T { precondition(index >= 0 && index < count, "index out of range") let val = storage[index]! for i in index..<(count - 1) { storage[i] = storage[i + 1] } storage[count - 1] = nil count -= 1 if count > 0 && count <= capacity / 4 { resize(to: max(1, capacity / 2)) } return val } subscript(i: Int) -> T { get { precondition(i >= 0 && i < count, "index out of range") return storage[i]! } set { precondition(i >= 0 && i < count, "index out of range") storage[i] = newValue } } }

欢迎大家来到IT世界,在知识的湖畔探索吧!

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!# 一个支持动态扩容/缩容的“底层数组”实现 # 使用 ctypes.py_object 作为底层存储以模拟真实 array import ctypes class DynamicArray: def __init__(self, initial_capacity=1): self.n = 0 # 实际元素个数 self.capacity = max(1, initial_capacity) # 容量 self.A = self._make_array(self.capacity) # 底层数组指针 def __len__(self): return self.n def __getitem__(self, index): if not 0 <= index < self.n: raise IndexError("index out of range") return self.A[index] def append(self, value): if self.n == self.capacity: self._resize(self.capacity * 2) self.A[self.n] = value self.n += 1 def insert(self, index, value): if not 0 <= index <= self.n: raise IndexError("index out of range") if self.n == self.capacity: self._resize(self.capacity * 2) # 右移 [index, n-1] for i in range(self.n, index, -1): self.A[i] = self.A[i - 1] self.A[index] = value self.n += 1 def remove_at(self, index): if not 0 <= index < self.n: raise IndexError("index out of range") val = self.A[index] # 左移 [index+1, n-1] for i in range(index, self.n - 1): self.A[i] = self.A[i + 1] self.A[self.n - 1] = None self.n -= 1 if 0 < self.n <= self.capacity // 4: self._resize(max(1, self.capacity // 2)) return val def _resize(self, new_cap): B = self._make_array(new_cap) for i in range(self.n): B[i] = self.A[i] self.A = B self.capacity = new_cap def _make_array(self, c): return (c * ctypes.py_object)()

1.2 大小固定的有序数组，支持动态增删改

思路：初始化给定容量 capacity，维护 count 与局部有序区间 [0, count)；

• insert(x): 二分定位插入点 → 右移 → 放入• remove(value or index): 定位 → 左移腾空• update(index, newValue): 为保持有序，通常“删除原值 + 重新插入”

Swift

/// 固定容量的有序数组（升序），支持增删改 struct SortedFixedArray<T: Comparable> { private var storage: [T?] private(set) var count: Int = 0 let capacity: Int init(capacity: Int) { precondition(capacity > 0) self.capacity = capacity self.storage = Array<T?>(repeating: nil, count: capacity) } func toArray() -> [T] { (0..<count).map { storage[$0]! } } // 二分查找插入位置（lower_bound） private func lowerBound(_ x: T) -> Int { var lo = 0, hi = count while lo < hi { let mid = (lo + hi) >> 1 if storage[mid]! < x { lo = mid + 1 } else { hi = mid } } return lo } // 插入：成功返回 true；满则返回 false mutating func insert(_ x: T) -> Bool { guard count < capacity else { return false } let idx = lowerBound(x) for i in stride(from: count, to: idx, by: -1) { storage[i] = storage[i - 1] } storage[idx] = x count += 1 return true } // 删除指定下标 @discardableResult mutating func remove(at index: Int) -> T? { guard index >= 0 && index < count else { return nil } let val = storage[index] for i in index..<(count - 1) { storage[i] = storage[i + 1] } storage[count - 1] = nil count -= 1 return val } // 删除指定值（如果存在多个，删除第一个） mutating func remove(value x: T) -> Bool { let idx = lowerBound(x) if idx < count, storage[idx]! == x { _ = remove(at: idx) return true } return false } // 更新：为了保持有序，采用“删除+重新插入”的方式 mutating func update(at index: Int, to newValue: T) -> Bool { guard index >= 0 && index < count else { return false } let old = storage[index]! // 若新值仍能处于原地有序，也可直接调整，但通用做法最稳妥： _ = remove(at: index) return insert(newValue) || { // 如果插入失败（容量满），回滚 _ = insert(old) return false }() } }

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!# 固定容量的有序数组（升序） class SortedFixedArray: def __init__(self, capacity): assert capacity > 0 self.capacity = capacity self.count = 0 self.a = [None] * capacity def to_list(self): return [self.a[i] for i in range(self.count)] def _lower_bound(self, x): lo, hi = 0, self.count while lo < hi: mid = (lo + hi) // 2 if self.a[mid] < x: lo = mid + 1 else: hi = mid return lo def insert(self, x): if self.count >= self.capacity: return False idx = self._lower_bound(x) for i in range(self.count, idx, -1): self.a[i] = self.a[i - 1] self.a[idx] = x self.count += 1 return True def remove_at(self, index): if not 0 <= index < self.count: return None val = self.a[index] for i in range(index, self.count - 1): self.a[i] = self.a[i + 1] self.a[self.count - 1] = None self.count -= 1 return val def remove_value(self, x): idx = self._lower_bound(x) if idx < self.count and self.a[idx] == x: self.remove_at(idx) return True return False def update(self, index, new_value): if not 0 <= index < self.count: return False old = self.a[index] self.remove_at(index) if not self.insert(new_value): # 回滚 self.insert(old) return False return True

1.3 实现两个有序数组合并为一个有序数组（稳定）

Swift

/// 归并两个升序数组（稳定） /// - 复杂度：O(n + m) func mergeSorted<T: Comparable>(_ a: [T], _ b: [T]) -> [T] { var i = 0, j = 0 var res: [T] = [] res.reserveCapacity(a.count + b.count) while i < a.count && j < b.count { if a[i] <= b[j] { // 稳定性：相等时先取 a res.append(a[i]); i += 1 } else { res.append(b[j]); j += 1 } } if i < a.count { res.append(contentsOf: a[i...]) } if j < b.count { res.append(contentsOf: b[j...]) } return res }

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!def merge_sorted(a, b): """稳定合并两个升序列表，O(n+m)""" i = j = 0 res = [] while i < len(a) and j < len(b): if a[i] <= b[j]: # 稳定：相等先取 a[i] res.append(a[i]); i += 1 else: res.append(b[j]); j += 1 if i < len(a): res.extend(a[i:]) if j < len(b): res.extend(b[j:]) return res

2) 链表（Linked List）

2.1 实现单链表、循环链表、双向链表（支持增删）

Swift

// MARK: - 单链表 final class SListNode<T> { var val: T var next: SListNode? init(_ v: T, _ next: SListNode? = nil) { self.val = v; self.next = next } } final class SinglyLinkedList<T: Equatable> { private(set) var head: SListNode<T>? private(set) var tail: SListNode<T>? private(set) var count: Int = 0 // 头插 func prepend(_ x: T) { let node = SListNode(x, head) head = node if tail == nil { tail = node } count += 1 } // 尾插 func append(_ x: T) { let node = SListNode(x) if let t = tail { t.next = node tail = node } else { head = node; tail = node } count += 1 } // 按值删除（删首个匹配） @discardableResult func removeFirst(_ x: T) -> Bool { var prev: SListNode<T>? = nil var cur = head while let c = cur { if c.val == x { if let p = prev { p.next = c.next if c.next == nil { tail = p } } else { // 删除头 head = c.next if head == nil { tail = nil } } count -= 1 return true } prev = cur cur = c.next } return false } // 删除头结点 @discardableResult func removeHead() -> T? { guard let h = head else { return nil } head = h.next if head == nil { tail = nil } count -= 1 return h.val } } // MARK: - 循环单链表（tail.next 指回 head） final class CircularLinkedList<T: Equatable> { private(set) var tail: SListNode<T>? // 仅持有 tail：tail.next 即 head private(set) var count = 0 var head: SListNode<T>? { tail?.next } var isEmpty: Bool { tail == nil } // 头插（在 tail 后插入新节点成为新 head） func prepend(_ x: T) { let node = SListNode(x) if let t = tail { node.next = t.next t.next = node } else { node.next = node // 自环 tail = node } count += 1 } // 尾插（让新节点成为 tail） func append(_ x: T) { prepend(x) // 先按头插逻辑放到 head 处 tail = tail?.next // 再把 tail 往前挪一个，使其成为真正尾结点 } // 删除头结点 @discardableResult func removeHead() -> T? { guard let t = tail else { return nil } let h = t.next! if h === t { // 仅一个节点 tail = nil } else { t.next = h.next // 跳过头节点 } count -= 1 return h.val } // 删除首个值为 x 的结点 func removeFirst(_ x: T) -> Bool { guard var prev = tail else { return false } var cur = prev.next for _ in 0..<count { if cur!.val == x { if cur === prev { // 仅一个节点且匹配 tail = nil } else { prev.next = cur!.next if cur === tail { tail = prev } // 删除的是 tail } count -= 1 return true } prev = cur! cur = cur!.next } return false } } // MARK: - 双向链表 final class DListNode<T> { var val: T var prev: DListNode? var next: DListNode? init(_ v: T) { self.val = v } } final class DoublyLinkedList<T: Equatable> { private(set) var head: DListNode<T>? private(set) var tail: DListNode<T>? private(set) var count = 0 func prepend(_ x: T) { let node = DListNode(x) node.next = head head?.prev = node head = node if tail == nil { tail = node } count += 1 } func append(_ x: T) { let node = DListNode(x) node.prev = tail tail?.next = node tail = node if head == nil { head = node } count += 1 } // 删除首个值为 x 的结点 func removeFirst(_ x: T) -> Bool { var cur = head while let c = cur { if c.val == x { let p = c.prev let n = c.next p?.next = n n?.prev = p if c === head { head = n } if c === tail { tail = p } count -= 1 return true } cur = c.next } return false } @discardableResult func removeHead() -> T? { guard let h = head else { return nil } let n = h.next n?.prev = nil head = n if head == nil { tail = nil } count -= 1 return h.val } }

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!# ---------- 单链表 ---------- class SNode: def __init__(self, val, nxt=None): self.val = val self.next = nxt class SinglyLinkedList: def __init__(self): self.head = None self.tail = None self.count = 0 def prepend(self, x): node = SNode(x, self.head) self.head = node if self.tail is None: self.tail = node self.count += 1 def append(self, x): node = SNode(x) if self.tail: self.tail.next = node self.tail = node else: self.head = self.tail = node self.count += 1 def remove_first(self, x): prev, cur = None, self.head while cur: if cur.val == x: if prev: prev.next = cur.next if cur.next is None: self.tail = prev else: self.head = cur.next if self.head is None: self.tail = None self.count -= 1 return True prev, cur = cur, cur.next return False def remove_head(self): if not self.head: return None val = self.head.val self.head = self.head.next if self.head is None: self.tail = None self.count -= 1 return val # ---------- 循环单链表 ---------- class CircularLinkedList: def __init__(self): self.tail = None self.count = 0 @property def head(self): return self.tail.next if self.tail else None def prepend(self, x): node = SNode(x) if self.tail: node.next = self.tail.next self.tail.next = node else: node.next = node self.tail = node self.count += 1 def append(self, x): self.prepend(x) self.tail = self.tail.next # 新节点成为 tail def remove_head(self): if not self.tail: return None h = self.tail.next val = h.val if h is self.tail: # 仅一个节点 self.tail = None else: self.tail.next = h.next self.count -= 1 return val def remove_first(self, x): if not self.tail: return False prev = self.tail cur = prev.next for _ in range(self.count): if cur.val == x: if cur is prev: # 仅一个节点 self.tail = None else: prev.next = cur.next if cur is self.tail: self.tail = prev self.count -= 1 return True prev, cur = cur, cur.next return False # ---------- 双向链表 ---------- class DNode: def __init__(self, val): self.val = val self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.tail = None self.count = 0 def prepend(self, x): node = DNode(x) node.next = self.head if self.head: self.head.prev = node self.head = node if self.tail is None: self.tail = node self.count += 1 def append(self, x): node = DNode(x) node.prev = self.tail if self.tail: self.tail.next = node self.tail = node if self.head is None: self.head = node self.count += 1 def remove_first(self, x): cur = self.head while cur: if cur.val == x: p, n = cur.prev, cur.next if p: p.next = n if n: n.prev = p if cur is self.head: self.head = n if cur is self.tail: self.tail = p self.count -= 1 return True cur = cur.next return False def remove_head(self): if not self.head: return None val = self.head.val n = self.head.next if n: n.prev = None self.head = n if self.head is None: self.tail = None self.count -= 1 return val

2.2 实现单链表反转

Swift

/// 迭代反转单链表：O(n) 时间，O(1) 额外空间 func reverseList<T>(_ head: SListNode<T>?) -> SListNode<T>? { var prev: SListNode<T>? = nil var cur = head while let c = cur { let nxt = c.next c.next = prev prev = c cur = nxt } return prev }

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!def reverse_list(head): prev, cur = None, head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

2.3 实现两个有序的链表合并为一个有序链表

Swift

/// 合并两个升序单链表（稳定） func mergeTwoSortedLists<T: Comparable>( _ l1: SListNode<T>?, _ l2: SListNode<T>? ) -> SListNode<T>? { let dummy = SListNode<T?>(nil) var tail: SListNode<T?>? = dummy var a = l1, b = l2 while let x = a, let y = b { if x.val <= y.val { // 稳定：相等时取 l1 tail?.next = SListNode<T?>(x.val) a = x.next } else { tail?.next = SListNode<T?>(y.val) b = y.next } tail = tail?.next } while let x = a { tail?.next = SListNode<T?>(x.val); tail = tail?.next; a = x.next } while let y = b { tail?.next = SListNode<T?>(y.val); tail = tail?.next; b = y.next } // 将可选节点链转成非可选值节点链（也可直接用非可选泛型配合复用节点） var p = dummy.next var head: SListNode<T>? = nil var q: SListNode<T>? = nil while let node = p { let t = SListNode(node.val!) // 解包 if head == nil { head = t; q = t } else { q?.next = t; q = t } p = node.next } return head }

说明：上面用 SListNode<T?> 作为中间拼接，最后转回 SListNode<T>。工程实践中，你也可以直接重用原节点指针来“原地合并”，如下更简洁版本（推荐）：

欢迎大家来到IT世界,在知识的湖畔探索吧!func mergeTwoSortedListsInPlace<T: Comparable>( _ a: SListNode<T>?, _ b: SListNode<T>? ) -> SListNode<T>? { let dummy = SListNode<T>(.init as! T) // 仅为占位，不会被读取 var tail: SListNode<T>? = dummy var p = a, q = b while let x = p, let y = q { if x.val <= y.val { tail?.next = x; p = x.next } else { tail?.next = y; q = y.next } tail = tail?.next } tail?.next = p ?? q return dummy.next }

注：dummy 的初始化在 Swift 上面这种写法只是为了占位示范，生产中可改为写成 SListNode<T>(x.val) 方式借助首元素初始化，或将 SListNode 的 val 改为可选以更自然地创建 dummy。

Python

def merge_two_sorted_lists(a, b): """稳定合并两个升序单链表，返回新链表头""" dummy = SNode(0) tail = dummy p, q = a, b while p and q: if p.val <= q.val: # 稳定：相等先取 p tail.next = p p = p.next else: tail.next = q q = q.next tail = tail.next tail.next = p or q return dummy.next

2.4 实现求链表的中间结点

快慢指针：slow 每次一步，fast 每次两步；当 fast 抵达末尾，slow 即中点。
约定：长度为偶数时，返回“
上中点”或“下中点”皆可，这里返回上中点（与“LeetCode 876 返回下中点”略有区别；若要下中点，可在循环条件上做微调）。

Swift

欢迎大家来到IT世界,在知识的湖畔探索吧!/// 返回单链表的“上中点”（偶数个节点时返回靠前的那个） /// 若希望“下中点”，可将 while 条件改为：while fast != nil && fast!.next != nil func middleNode<T>(_ head: SListNode<T>?) -> SListNode<T>? { var slow = head var fast = head while let f = fast, let nn = f.next?.next { slow = slow?.next fast = nn } return slow }

Python

def middle_node(head): """返回单链表的上中点；若要下中点，将 while 条件改为 while fast and fast.next:""" slow = fast = head while fast and fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow

小结（如何选择与复习要点）

• • 数组：随机访问 O(1)，插入/删除（中间位置）O(n)；动态扩容常用倍增策略。
• • 有序数组：二分查找 O(log n)，插入/删除仍需搬移 O(n)。
• • 链表：插入/删除 O(1)（已定位节点后），访问第 k 个元素 O(k)。
• • 典型技巧：三数之和
• 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
  注意：答案中不可以包含重复的三元组。
  
• • 快慢指针（中点、是否成环、倒数第 k 个）；
• • 归并（合并两个有序序列/链表）；
• • 原地反转（迭代三指针）。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

下面给出标准做法（排序 + 双指针，时间复杂度 ；通过“跳过相同元素”彻底去重），并分别提供 Python 与 Swift 代码。

思路速览

1. 1. 先将数组升序排序。
2. 2. 枚举第一个数 （只保留每个值的第一次出现，若 a[i] > 0 可提前结束）。
3. 3. 对区间 (i, end] 用双指针 l, r 寻找和为 -a[i] 的两数：
4. • 和为 0：记录三元组，然后同时内缩 l+=1, r-=1，并跳过重复值；
5. • 和 < 0：l+=1；
6. • 和 > 0：r-=1。
7. 4. 去重关键：
8. • 外层：i > 0 && a[i] == a[i-1] 时跳过；
9. • 内层：找到一个解后，while l<r && a[l]==a[l-1] 以及 while l<r && a[r]==a[r+1] 跳过重复。

Python 实现

欢迎大家来到IT世界,在知识的湖畔探索吧!from typing import List def threeSum(nums: List[int]) -> List[List[int]]: """ 返回所有不重复、和为 0 的三元组。 时间复杂度：O(n^2)，空间复杂度：O(1)（不计输出，排序为 O(log n) 递归栈） """ nums.sort() n = len(nums) res: List[List[int]] = [] for i in range(n - 2): # 去重：只使用某个值作为首元素的一次机会 if i > 0 and nums[i] == nums[i - 1]: continue # 剪枝：如果首元素已大于 0，后面都 >= 首元素，和不可能为 0 if nums[i] > 0: break l, r = i + 1, n - 1 while l < r: s = nums[i] + nums[l] + nums[r] if s == 0: res.append([nums[i], nums[l], nums[r]]) l += 1 r -= 1 # 跳过 l 的重复值 while l < r and nums[l] == nums[l - 1]: l += 1 # 跳过 r 的重复值 while l < r and nums[r] == nums[r + 1]: r -= 1 elif s < 0: l += 1 else: r -= 1 return res # 简单自测 if __name__ == "__main__": print(threeSum([-1,0,1,2,-1,-4])) # -> [[-1, -1, 2], [-1, 0, 1]] print(threeSum([0,1,1])) # -> [] print(threeSum([0,0,0])) # -> [[0,0,0]]

Swift 实现

import Foundation class Solution { /// 返回所有不重复、和为 0 的三元组 /// - Complexity: O(n^2) time, O(1) extra space (excluding output) func threeSum(_ nums: [Int]) -> [[Int]] { let a = nums.sorted() let n = a.count var res = [[Int]]() if n < 3 { return res } var i = 0 while i < n - 2 { // 去重：只使用某个值作为首元素的一次机会 if i > 0 && a[i] == a[i - 1] { i += 1 continue } // 剪枝：首元素已 > 0，无解 if a[i] > 0 { break } var l = i + 1 var r = n - 1 while l < r { let s = a[i] + a[l] + a[r] if s == 0 { res.append([a[i], a[l], a[r]]) l += 1 r -= 1 // 跳过 l 的重复值 while l < r && a[l] == a[l - 1] { l += 1 } // 跳过 r 的重复值 while l < r && a[r] == a[r + 1] { r -= 1 } } else if s < 0 { l += 1 } else { r -= 1 } } i += 1 } return res } } // 简单自测 let sol = Solution() print(sol.threeSum([-1,0,1,2,-1,-4])) // [[-1, -1, 2], [-1, 0, 1]] print(sol.threeSum([0,1,1])) // [] print(sol.threeSum([0,0,0])) // [[0, 0, 0]]

复杂度 & 细节

• • 时间：排序 + 双指针枚举 ，总体 。
• • 空间：除返回结果外为 ；排序的栈/实现细节忽略不计。
• • 正确去重的两个层面（外层 i 与内层 l/r）是避免重复三元组的关键。

求众数

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1： 输入：nums = [3,2,3] 输出：3

示例 2： 输入：nums = [2,2,1,1,1,2,2] 输出：2 提示： n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

下面给出满足进阶要求 O(n) 时间、O(1) 空间 的解法——Boyer–Moore 多数投票算法，并提供 Python 与 Swift 代码。

思路（Boyer–Moore Majority Vote）

把数组元素想成选票：

• • 维护一个 candidate（候选人）与计数 count。
• • 遍历数组：
• • 若 count == 0，把当前元素设为 candidate，count = 1；
• • 否则如果当前元素等于 candidate，count += 1；
• • 否则 count -= 1。
  直觉：非多数元素最终会被“两两抵消”掉，多数元素因“超半数”而留下成为候选。题目保证多数元素存在，因此最后的 candidate 即答案。
  

复杂度：时间 O(n)，空间 O(1)。

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!from typing import List def majorityElement(nums: List[int]) -> int: candidate = None count = 0 for x in nums: if count == 0: candidate = x count = 1 elif x == candidate: count += 1 else: count -= 1 return candidate # 题目保证一定存在多数元素 # 示例 print(majorityElement([3,2,3])) # 3 print(majorityElement([2,2,1,1,1,2,2])) # 2

Swift

import Foundation class Solution { func majorityElement(_ nums: [Int]) -> Int { var candidate = 0 var count = 0 for x in nums { if count == 0 { candidate = x count = 1 } else if x == candidate { count += 1 } else { count -= 1 } } return candidate // 题目保证存在多数元素 } } // 示例 let sol = Solution() print(sol.majorityElement([3,2,3])) // 3 print(sol.majorityElement([2,2,1,1,1,2,2])) // 2

正确性要点

把所有非 candidate 的票与 candidate 成对消去；多数元素的票数 > 其他元素之和，因此在任何消去过程中它不可能被完全抵消，最终留为候选。题设保证存在多数元素，所以无需二次验证。若没有此保证，可再做一次计数验证。

求缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 – 1

下面给出满足 O(n) 时间、O(1) 额外空间 的经典解法：原地哈希（下标放置 / 循环交换）。并提供 Python 与 Swift 代码。

思路（原地哈希 / 循环交换）

• • 结论：长度为 n 的数组中，最小缺失正整数一定落在 [1..n+1]。
• • 做法：把每个处在区间 [1..n] 的值 v 放到它“应该在的位置”——下标 v-1 上。
  实现上用 while + swap：
  
• • 当 nums[i] 在 [1..n] 且 nums[nums[i]-1] != nums[i] 时，把它交换到目标位；
• • 否则 i += 1 往后扫。
• • 最后第一个满足 nums[i] != i+1 的位置，其答案即为 i+1；若都正确归位，则答案是 n+1。

复杂度：每个元素最多被交换到位一次，整体 O(n)；仅用到常数个临时变量，空间 O(1)（不计输入输出）。

Python 实现

欢迎大家来到IT世界,在知识的湖畔探索吧!from typing import List def firstMissingPositive(nums: List[int]) -> int: n = len(nums) i = 0 while i < n: v = nums[i] # 仅当 v 在 [1..n] 且不在正确位置时，执行交换 if 1 <= v <= n and nums[v - 1] != v: nums[i], nums[v - 1] = nums[v - 1], nums[i] # 此处不要 i += 1，交换过来新的 nums[i] 还需检查 else: i += 1 # 扫描寻找第一个没对上的位置 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1 # 示例 if __name__ == "__main__": print(firstMissingPositive([1,2,0])) # 3 print(firstMissingPositive([3,4,-1,1])) # 2 print(firstMissingPositive([7,8,9,11,12])) # 1

Swift 实现

import Foundation class Solution { // 不修改外部数组：内部复制一份做原地操作 func firstMissingPositive(_ nums: [Int]) -> Int { var a = nums let n = a.count var i = 0 while i < n { let v = a[i] // 当 v 在 [1..n] 且不在正确位置时，把它交换到 v-1 的位置 if v >= 1 && v <= n && a[v - 1] != v { a.swapAt(i, v - 1) // 不前进 i：交换来的新值还要继续检查 } else { i += 1 } } // 扫描第一个不匹配的位置 for i in 0..<n { if a[i] != i + 1 { return i + 1 } } return n + 1 } } // 示例 let sol = Solution() print(sol.firstMissingPositive([1,2,0])) // 3 print(sol.firstMissingPositive([3,4,-1,1])) // 2 print(sol.firstMissingPositive([7,8,9,11,12])) // 1

细节与边界

• • 重复值：交换条件 a[v-1] != v 保证不会无限交换。
• • 无效值：<=0 或 >n 的统统跳过，不会影响答案。
• • 答案范围：若 [1..n] 全到位，则最小缺失就是 n+1。

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

下面给出判环的标准做法：快慢指针（Floyd 判圈算法）。
思路：用两个指针同时从头出发，slow 每次走一步，fast 每次走两步；若存在环，它们最终会在环内相遇；若 fast 或 fast.next 先为 null，说明无环。

复杂度：时间 ，空间 。

Python

欢迎大家来到IT世界,在知识的湖畔探索吧!# 单链表结点定义（题目平台一般已给出） class ListNode: def __init__(self, x, nxt=None): self.val = x self.next = nxt def hasCycle(head: ListNode) -> bool: slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # 引用相等 => 指向同一结点 return True return False # 简单构造：1 -> 2 -> 3 -> 4 -> 2(成环) if __name__ == "__main__": n1, n2, n3, n4 = ListNode(1), ListNode(2), ListNode(3), ListNode(4) n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2 print(hasCycle(n1)) # True

备注：也可用哈希集合记录访问过的结点 id 来判环，但那是 额外空间，不满足进阶空间要求。

Swift

// 单链表结点定义（LeetCode 已内置该结构体/类时可忽略） public class ListNode { public var val: Int public var next: ListNode? public init(_ val: Int) { self.val = val; self.next = nil } } func hasCycle(_ head: ListNode?) -> Bool { var slow = head var fast = head // 只要 fast 和 fast?.next 都非空就能继续推进 while let f = fast, let fn = f.next { slow = slow?.next fast = fn.next if slow === fast { return true } // 引用同一结点 => 有环 } return false } // 演示：1 -> 2 -> 3 -> 4 -> 2(成环) let n1 = ListNode(1), n2 = ListNode(2), n3 = ListNode(3), n4 = ListNode(4) n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2 print(hasCycle(n1)) // true

这就是全部：用快慢指针即可在 / 内判断链表是否存在环。

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

下面给出两种常用解法，并提供 Python（最小堆） 与 Swift（分治合并） 代码。时间复杂度都为 （ 为所有节点总数， 为链表数量），空间分别为 与 额外栈/辅助结构（不计输出）。

解法一：最小堆（Python，heapq）

思路：把每条链表的头结点放入小根堆；每次弹出最小结点接到结果链表，并将其后继压回堆。

欢迎大家来到IT世界,在知识的湖畔探索吧!from typing import List, Optional import heapq class ListNode: def __init__(self, val=0, nxt=None): self.val = val self.next = nxt def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 小根堆：元素为 (节点值, 唯一序号, 节点) heap = [] uid = 0 for node in lists: if node: heapq.heappush(heap, (node.val, uid, node)) uid += 1 dummy = ListNode() tail = dummy while heap: _, _, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, uid, node.next)) uid += 1 return dummy.next

• • 时间：建堆 ，每弹/压一次为 ，共 次 → 。
• • 空间：堆中最多存 个节点 → 。

解法二：分治合并（Swift）

思路：两两合并；将区间 [l, r] 的链表递归拆分为两半，各自合并后再合并为一条。

// LeetCode 提供的定义 public class ListNode { public var val: Int public var next: ListNode? public init() { self.val = 0; self.next = nil } public init(_ val: Int) { self.val = val; self.next = nil } public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next } } class Solution { func mergeKLists(_ lists: [ListNode?]) -> ListNode? { guard !lists.isEmpty else { return nil } return mergeRange(lists, 0, lists.count - 1) } private func mergeRange(_ lists: [ListNode?], _ l: Int, _ r: Int) -> ListNode? { if l == r { return lists[l] } let m = (l + r) >> 1 let left = mergeRange(lists, l, m) let right = mergeRange(lists, m + 1, r) return mergeTwo(left, right) } // 合并两个有序链表（原地指针法） private func mergeTwo(_ a: ListNode?, _ b: ListNode?) -> ListNode? { let dummy = ListNode() var tail: ListNode? = dummy var p = a, q = b while let x = p, let y = q { if x.val <= y.val { tail?.next = x p = x.next } else { tail?.next = y q = y.next } tail = tail?.next } tail?.next = p ?? q return dummy.next } }

• • 时间：每层合并代价 ，层数 → 。
• • 空间：递归深度 （栈），额外常数级指针。

备注：Swift 也可实现最小堆，但分治代码更短、同复杂度。Python 同样可用分治；两种思路任选其一即可。