AnyJohn 的网络博客

算法解题思路：边界条件与返回值

Properties1
tags算法, 笔记, 面试

12分钟阅读

算法解题思路：边界条件与返回值

做算法题时，思路对了但代码过不了，通常死在两个地方：边界条件漏判，返回值搞错。这两个问题不涉及算法设计，纯粹是工程习惯。下面是从实战和资料中总结的方法，适用于链表、数组、树、字符串等各类题目。

根因：过程思维 vs 契约思维

写代码时容易陷入过程思维——关注”当前这步在做什么”。比如删链表节点时，脑子里想的是”找到前驱，改 next 指针”。但到了 return 的时候，顺手返回了刚刚操作的节点，而不是调用方真正需要的链表头。

契约思维关注的是函数的输入和输出。函数接收一个 head，调用方需要的是新链表的头节点。你刚操作的 preNode 是中间某个节点，拿它当返回值没用。

这个问题不限于链表。写二分查找时，关注的是”缩小搜索区间”，但 return 的是 left 还是 right 还是 mid？写树的遍历时，关注的是”先左后右”，但返回的是节点值列表还是节点本身？写字符串匹配时，关注的是”滑动窗口”，但返回的是索引还是长度还是子串？

“我正在操作的东西” ≠ “函数应该返回的东西”。

方法一：写代码前先写函数契约

动笔之前，用注释列出三个问题：

// 输入：head（链表头），k（要删的节点偏移量）
// 输出：新链表的 head
// 边界：head=null? k=0(删最后一个)? k=n-1(删head)? k越界?

缺的往往就是”输出”这一行。写了这行，在 return preNode 的时候就会停一下。

不同类型的题目，契约的重点不同：

题型输入要点输出要点边界要点
链表head 是否为 null返回 head 还是新结构空/单节点/删 head
数组是否空数组返回索引还是值还是新数组空数组/单元素/全相同
二叉树root 是否为 null返回值列表还是节点空/单节点/只有左子树或右子树
字符串是否空串返回索引还是长度还是子串空串/单字符/全相同字符
二分查找数组是否有序返回 left 还是 right目标不存在/目标在两端

方法二：列出所有边界场景，每个对应一个返回值

以”删除链表倒数第 k 个节点”为例：

场景返回什么
head = nullnull
删 head（k = n-1）head.next
删中间或尾部head（原 head 不变）
k 越界head（原样返回）

写代码前先填这张表。分支数和返回值一目了然，不容易写错。

再看一个数组题的例子——二分查找：

场景返回什么
数组为空-1
目标存在mid
目标不存在-1（或 left，取决于变体）
目标在两端mid（不要漏掉首尾）

再看字符串题——最长无重复子串：

场景返回什么
空串0
单字符1
全部相同字符1
全部不同s.length

方法相同，只是边界不同。核心动作是：写代码前先填表，每个分支对应一个返回值。

方法三：用哨兵/占位消灭分支

链表用 dummy 节点，数组用哨兵值，树用 null 返回。目的都一样：消灭特殊分支。

interviewing.io 的文章指出：dummy 节点能”eliminate the need to handle the edge case where the node to be deleted is the head of the list separately”。

不用 dummy 的链表代码，删 head 和删中间是两套逻辑：

# 不用 dummy：删 head 要特殊处理
if self.head.data == data:
    self.head = self.head.next
    return
current_node = self.head
while current_node.next is not None:
    if current_node.next.data == data:
        current_node.next = current_node.next.next
        return
    current_node = current_node.next

用 dummy 后，删 head 和删中间变成一条路径：

# 用 dummy：统一操作，不管删的是不是 head
dummy = ListNode(0)
dummy.next = head
current = dummy
while current.next:
    if current.next.val == val:
        current.next = current.next.next
    else:
        current = current.next
return dummy.next  # 自动追踪新 head

数组也有类似技巧。比如归并排序的 merge 阶段，在数组末尾放一个哨兵值（无穷大），就不用单独处理一个数组先结束的情况：

# 不用哨兵：一个数组先结束要单独处理
while i < len(A) and j < len(B):
    if A[i] <= B[j]:
        result.append(A[i])
        i += 1
    else:
        result.append(B[j])
        j += 1
# 还要处理剩余元素
while i < len(A):
    result.append(A[i])
    i += 1
while j < len(B):
    result.append(B[j])
    j += 1
# 用哨兵：A 和 B 末尾各加一个无穷大，一个数组结束就自动走另一个
A.append(float('inf'))
B.append(float('inf'))
i = j = 0
for _ in range(len(A) + len(B) - 2):
    if A[i] <= B[j]:
        result.append(A[i])
        i += 1
    else:
        result.append(B[j])
        j += 1

分支越少，返回值出错的机会越少。Google AI 概览总结的核心原则是：“Always return dummy.next”。

方法四：提交前检查清单

Google AI 概览给出了一个面试检查清单，推广到所有题型：

  1. 空输入检查了吗？ head = null / 数组为空 / 字符串为空 / root = null
  2. 单元素检查了吗？ 单节点 / 单元素数组 / 单字符 / 只有一个节点的树
  3. 首尾边界检查了吗？ 删 head / 数组首元素 / 字符串首尾 / 树的叶子节点
  4. 循环终止条件会不会导致越界？ null.next / 数组越界 / 空指针

每次写完代码，过一遍这四条。不需要花太多时间，10 秒够了。

方法五：结构变化类问题用辅助变量

当数据结构整体变化时，入口指针必然改变。用辅助变量追踪新入口：

链表反转——head 变成 tail，用 prev 追踪新 head：

prev = None
current = head
while current:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
return prev  # prev 停在新 head 上

数组原地反转——首尾交换，用双指针追踪边界：

left, right = 0, len(arr) - 1
while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1
return arr

二叉树合并——生成新树，用新节点追踪结果：

def mergeTrees(t1, t2):
    if not t1 and not t2: return None
    if not t1: return t2
    if not t2: return t1
    node = TreeNode(t1.val + t2.val)
    node.left = mergeTrees(t1.left, t2.left)
    node.right = mergeTrees(t1.right, t2.right)
    return node

Google AI 概览的原则是：“Return the auxiliary pointer, not the original head”。因为循环结束后，辅助指针自然停在新入口的位置。推广到所有结构变化类问题：返回追踪变化结果的辅助变量，不是原始输入。

方法六：跑测试验证

写完代码后，不要只靠大脑模拟。写几个测试用例跑一遍：

  • 正常场景：中间值、典型输入
  • 边界场景：空输入、单元素、首尾元素
  • 越界/异常场景：超出范围、全相同、极端大/小

不同题型的测试清单：

题型正常场景边界场景异常场景
链表删中间空/单节点/删 headk 越界
数组中间元素空数组/单元素目标不存在
树完整树空/单节点/只有左子树退化成链表
字符串正常匹配空串/单字符全相同/全不同
二分查找目标在中间单元素数组目标在两端

测试用例比推理 10 分钟管用。大脑模拟容易漏边界，测试不会。

常见坑总结

interviewing.io 总结了链表面试中最常见的错误，推广到所有题型：

  1. 不检查 null/空就访问属性：链表 tail.next.data、数组 arr[0]（空数组）、树 root.left（root 为 null）、字符串 s[0]（空串）。
  2. 不用哨兵/占位：导致首尾边界写成两套逻辑，容易出错。
  3. 忽略首尾边界：链表的 head/tail、数组的首尾元素、树的叶子节点、字符串的首尾字符——这些是最常见的操作位置，也是最容易被忽略的边界。

总结

方法核心动作适用题型
函数契约写代码前先写”输入/输出/边界”注释所有
边界表列出每个边界场景和对应返回值所有
哨兵/占位用 dummy/哨兵值/null 消灭 if-else 分支链表/数组/树
检查清单空输入? 单元素? 首尾? 越界?所有
辅助变量结构变化时用辅助变量追踪新入口链表/数组/树
跑测试不要只靠大脑模拟，写用例跑一遍所有

核心思路就一句话：“我正在操作的东西” ≠ “函数应该返回的东西”。 写代码时关注当前步骤，但 return 之前停 10 秒，想想调用方需要什么。

完整的解题流程见 算法解题流程：从读题到提交的七步。

参考来源

Graph View

反向链接

近期发布