Swift 解法详解：LeetCode 369《给单链表加一》

网罗开发（小红书、快手、视频号同名）

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：华为HDE/HDG

我的博客内容涵盖广泛，主要分享技术教程、Bug解决方案、开发工具使用、前沿科技资讯、产品评测与使用体验。我特别关注云服务产品评测、AI 产品对比、开发板性能测试以及技术报告，同时也会提供产品优缺点分析、横向对比，并分享技术沙龙与行业大会的参会体验。我的目标是为读者提供有深度、有实用价值的技术洞察与分析。

展菲：您的前沿技术领航员
👋 大家好，我是展菲！
📱 全网搜索“展菲”，即可纵览我在各大平台的知识足迹。
📣 公众号“Swift社区”，每周定时推送干货满满的技术长文，从新兴框架的剖析到运维实战的复盘，助您技术进阶之路畅通无阻。
💬 微信端添加好友“fzhanfei”，与我直接交流，不管是项目瓶颈的求助，还是行业趋势的探讨，随时畅所欲言。
📅 最新动态：2025 年 3 月 17 日
快来加入技术社区，一起挖掘技术的无限潜能，携手迈向数字化新征程！

摘要

这道题听起来很简单：在链表表示的整数上加一。但因为链表是单链表，而且数字是从高位到低位依次存放的，所以要正确处理进位就没那么直观了。我们不能像数组那样直接从最后一位开始往前走，因为链表的尾部不好倒着访问。

在这篇文章里，我会用一个清晰的思路来解释，如何优雅地处理这种进位问题，并给出 Swift 的完整实现。

描述

题目要求：
给定一个非空的单链表，它表示一个非负整数，链表的头节点是最高位。

要对这个数加一，并返回结果链表。

示例 1：

输入: 1 -> 2 -> 3
输出: 1 -> 2 -> 4
解释: 123 + 1 = 124

示例 2：

输入: 9 -> 9 -> 9
输出: 1 -> 0 -> 0 -> 0
解释: 999 + 1 = 1000

题解答案

链表问题的难点在于不能从后往前操作。解决这个问题有两种常见方法：

1. 反转链表：

   • 把链表反转过来，从低位开始加一，处理进位，再反转回来。

2. 递归：

   • 递归走到最后一个节点（最低位），先加一，再一路返回时处理进位。

这里我选择第二种递归的方法，更直观也更优雅。

题解代码分析

下面是 Swift 的完整实现：

import Foundation// 定义链表节点
public class ListNode {public var val: Intpublic var next: ListNode?public init(_ val: Int) {self.val = valself.next = nil}
}class Solution {func plusOne(_ head: ListNode?) -> ListNode? {// 递归处理加法let carry = dfs(head)// 如果最高位还有进位，需要新增一个节点if carry > 0 {let newHead = ListNode(carry)newHead.next = headreturn newHead}return head}// 递归函数：返回进位private func dfs(_ node: ListNode?) -> Int {guard let node = node else { return 1 } // 到尾部时，加 1let carry = dfs(node.next)let sum = node.val + carrynode.val = sum % 10return sum / 10}
}// MARK: - Demo 演示
func buildList(_ nums: [Int]) -> ListNode? {let dummy = ListNode(0)var current = dummyfor num in nums {current.next = ListNode(num)current = current.next!}return dummy.next
}func printList(_ head: ListNode?) {var current = headvar result = [String]()while let node = current {result.append(String(node.val))current = node.next}print(result.joined(separator: " -> "))
}let solution = Solution()// 示例 1
let list1 = buildList([1, 2, 3])
let result1 = solution.plusOne(list1)
printList(result1) // 输出: 1 -> 2 -> 4// 示例 2
let list2 = buildList([9, 9, 9])
let result2 = solution.plusOne(list2)
printList(result2) // 输出: 1 -> 0 -> 0 -> 0

代码拆解

1. 核心递归 dfs

   • 递归到底时返回 1，表示“加一”。
   • 往上返回时，每个节点都加上进位，再更新当前节点的值。
   • 返回新的进位（要么是 0，要么是 1）。

2. 处理头节点的进位

   • 如果最高位还带进位，比如 999 变成 1000，就需要新建一个头节点 1。

3. 构造链表与打印链表

   • 写了两个辅助函数 buildList 和 printList，方便测试。

示例测试及结果

执行代码，得到的结果如下：

输入: 1 -> 2 -> 3
输出: 1 -> 2 -> 4输入: 9 -> 9 -> 9
输出: 1 -> 0 -> 0 -> 0

符合题意，说明我们的解法正确。

时间复杂度

• 每个节点只访问一次，所以时间复杂度是 O(n)，其中 n 是链表长度。

空间复杂度

• 使用了递归调用栈，深度为 n，所以空间复杂度是 O(n)。
• 如果用反转链表的迭代写法，可以做到 O(1) 额外空间。

总结

这道题的核心是如何处理 链表尾部加一 的问题。因为链表没有办法反向访问，所以用递归或者反转链表是比较常见的思路。

• 递归解法思路清晰，写起来更简洁，但会用到 O(n) 的递归栈空间。
• 如果你追求极致性能，可以用“反转链表 + 迭代”的办法，做到 O(1) 额外空间。

这种题目在真实场景中也挺有意思，比如：

• 模拟超大整数的加法（超过 Int 的范围）。
• 在分布式存储里，每一位可能存放在不同节点上，只能顺序访问，不能直接随机访问。