Python刷题进阶：LeetCode链表与位运算专题解析

2026年3月6日 互联网

一、链表操作基础与进阶技巧

链表作为线性数据结构的核心代表，其操作涉及指针动态调整与边界条件处理，是算法面试的常考题型。本文选取四道经典题目，从基础操作到复杂场景逐步深入。

1.1 删除指定节点（LeetCode 203）

问题描述

给定链表头节点与整数x，要求删除所有值等于x的节点，并返回处理后的链表头节点。

关键突破点

  1. 虚拟头节点技术：传统方法需单独处理头节点删除场景，引入虚拟头节点可统一所有节点的删除逻辑。
  2. 双指针遍历：使用prev指针记录当前节点的前驱，避免每次删除后重新寻找前驱节点。
  1. class ListNode:
  2.     def __init__(self, val=0, next=None):
  3.         self.val = val
  4.         self.next = next
  6. def removeElements(head: ListNode, x: int) -> ListNode:
  7.     dummy = ListNode(next=head)  # 创建虚拟头节点
  8.     prev, curr = dummy, head
  10.     while curr:
  11.         if curr.val == x:
  12.             prev.next = curr.next  # 跳过待删除节点
  13.         else:
  14.             prev = curr  # 仅当不删除时移动prev
  15.         curr = curr.next
  17.     return dummy.next

复杂度分析

时间复杂度O(n)，空间复杂度O(1)，通过一次遍历完成所有删除操作。

1.2 两两交换节点（LeetCode 24）

问题描述

将链表中的节点两两交换，例如1→2→3→4变为2→1→4→3。

递归解法

  1. 终止条件：当链表为空或仅剩一个节点时直接返回
  2. 递归单元：交换前两个节点后，对剩余链表递归处理
  1. def swapPairs(head: ListNode) -> ListNode:
  2.     if not head or not head.next:
  3.         return head
  5.     new_head = head.next
  6.     head.next = swapPairs(new_head.next)
  7.     new_head.next = head
  9.     return new_head

迭代解法

使用三个指针pre、first、second完成局部交换：

  1. def swapPairs_iter(head: ListNode) -> ListNode:
  2.     dummy = ListNode(next=head)
  3.     pre = dummy
  5.     while pre.next and pre.next.next:
  6.         first = pre.next
  7.         second = pre.next.next
  9.         # 执行交换
  10.         pre.next = second
  11.         first.next = second.next
  12.         second.next = first
  14.         # 移动pre指针
  15.         pre = first
  17.     return dummy.next

1.3 分割链表（LeetCode 86）

问题描述

根据给定值x将链表分割为两部分，所有小于x的节点在前，大于等于x的节点在后，保持原有相对顺序。

双链表构建法

  1. 创建两个虚拟链表small_head和large_head
  2. 遍历原链表时，根据节点值将节点分别追加到对应链表
  3. 最后连接两个链表尾部
  1. def partition(head: ListNode, x: int) -> ListNode:
  2.     small_dummy = ListNode()
  3.     large_dummy = ListNode()
  4.     small_ptr, large_ptr = small_dummy, large_dummy
  6.     curr = head
  7.     while curr:
  8.         if curr.val < x:
  9.             small_ptr.next = curr
  10.             small_ptr = small_ptr.next
  11.         else:
  12.             large_ptr.next = curr
  13.             large_ptr = large_ptr.next
  14.         curr = curr.next
  16.     # 连接两个链表
  17.     small_ptr.next = large_dummy.next
  18.     large_ptr.next = None  # 防止链表循环
  20.     return small_dummy.next

二、位运算专题解析

位运算作为底层优化技术，在特定场景下能显著提升算法效率。本文以”只出现一次的数字”为例，解析位运算的应用。

2.1 异或运算特性

异或运算（^）具有以下重要性质：

  1. 任何数与0异或等于其本身：a ^ 0 = a
  2. 任何数与自身异或等于0：a ^ a = 0
  3. 异或运算满足交换律和结合律

2.2 只出现一次的数字（LeetCode 136）

问题描述

给定非空整数数组，除一个数字出现一次外，其余数字均出现两次，找出该数字。

位运算解法

利用异或运算的抵消特性，遍历数组进行累加异或：

  1. def singleNumber(nums: List[int]) -> int:
  2.     result = 0
  3.     for num in nums:
  4.         result ^= num
  5.     return result

复杂度优势

时间复杂度O(n)，空间复杂度O(1)，相比哈希表解法（O(n)空间）具有显著优势。

2.3 位运算扩展应用

  1. 判断奇偶：num & 1 == 1为奇数
  2. 交换变量：a ^= b; b ^= a; a ^= b
  3. 位掩码技术：通过位操作实现高效状态标记

三、算法优化方法论

3.1 边界条件处理

  1. 空链表处理：所有链表操作需首先判断head是否为None
  2. 单节点链表：明确是否需要特殊处理
  3. 循环终止条件：迭代解法中需准确设置终止条件

3.2 空间复杂度优化

  1. 原地操作：尽可能在原数据结构上进行修改
  2. 指针复用：通过巧妙指针移动减少额外空间使用
  3. 递归转迭代：将递归解法转换为迭代实现，避免栈空间消耗

3.3 时间复杂度分析

  1. 遍历次数：尽量将多次遍历合并为单次遍历
  2. 嵌套循环：警惕嵌套循环导致的O(n²)复杂度
  3. 数据结构选择：根据操作特点选择合适数据结构（如哈希表实现O(1)查找）

四、实战建议与学习路径

  1. 分阶段练习：从简单题目入手，逐步提升难度
  2. 多解法对比：对每个问题尝试多种解法，理解不同解法的优劣
  3. 代码重构：完成初版后进行代码优化，提升可读性与效率
  4. 模拟面试：通过计时练习培养时间管理能力
  5. 知识迁移：将链表操作技巧应用到树、图等其他数据结构

建议开发者建立错题本，记录典型错误与优化思路，定期进行复习总结。对于位运算等底层技术，可通过阅读《深入理解计算机系统》等经典著作加深理解。在掌握基础算法后，可尝试参与开源项目或算法竞赛，在实践中提升问题解决能力。

最新文章