跳到主要内容

两数相加：链表反转的加法艺术

引言：当链表学会做加法​

LeetCode第二题，链表操作的经典入门题。如果说两数之和是哈希表的开胃菜，那两数相加就是链表操作的必修课。多年开发经验告诉我：链表题的精髓不在复杂，而在边界处理的细腻。今天GO兔就带大家从青铜到黄金，一步步实现这个看似简单却暗藏玄机的算法。

一、青铜解法：小学生列竖式​

1.1 直观思路​

最容易想到的解法就像小学生列竖式——从最低位（链表头）开始逐位相加，记录进位，直到两个数都加完。就像两只倒着跑的兔子，要同步前进才能算出正确结果。

1.2 Go代码实现​

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0} // 哑节点，链表操作的万能钥匙
    current := dummy
    carry := 0 // 进位，像个跟屁虫一样跟着我们的计算
    
    // 只要还有数字没加完，或者还有进位，就继续算
    for l1 != nil || l2 != nil || carry > 0 {
        sum := carry
        
        // 加上l1当前节点的值（如果还有的话）
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next // 移到下一位，像兔子跳一步
        }
        
        // 加上l2当前节点的值（如果还有的话）
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next // 另一只兔子也跳一步
        }
        
        carry = sum / 10 // 计算进位，sum/10就像剥掉个位数
        current.Next = &ListNode{Val: sum % 10} // 个位数作为当前位结果
        current = current.Next // 结果指针也往前挪
    }
    
    return dummy.Next // 哑节点的下一个才是真正的头
}

1.3 复杂度分析​

  • 时间复杂度：O(max(m,n))，其中m和n分别是两个链表的长度。就像两只兔子赛跑，跑的快的等跑的慢的
  • 空间复杂度：O(1)，如果不算返回结果的话。我们只使用了几个额外变量

1.4 瑕疵​

代码虽然正确，但不够优雅。sum变量显得多余，变量声明可以更紧凑，就像穿着宽松的运动服跑步——能跑但不够利索。

二、那些坑人的边界情况​

2.1 不等长链表​

就像一只兔子跑得快，一只跑得慢：

  • 输入: (9->9->9->9->9->9->9), (9->9->9->9)
  • 输出: (8->9->9->9->0->0->0->1)

2.2 进位传递​

这进位像兔子跳格子一样一路传递：

  • 输入: (5), (5)
  • 输出: (0->1)

2.3 空链表处理​

题目说非空？但咱们的代码得像个全能选手，就算遇到空链表也得优雅应对——毕竟谁还没遇到过"空欢喜"呢：

  • 输入: (0), (0)
  • 输出: (0)

三、黄金解法：代码高尔夫​

3.1 核心优化​

去掉多余的sum变量，直接用carry累加；精简变量声明，让代码像短跑运动员一样轻盈。

3.2 Go代码实现​

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 创建哑节点 - 链表操作的"万能钥匙"，避免处理头节点的特殊情况
    dummy := &ListNode{}
    // current指针负责构建新链表，carry是进位小跟班
    current, carry := dummy, 0
    
    // 只要还有数字没加完，或者进位还在，就继续算（进位：我还能再战！）
    for l1 != nil || l2 != nil || carry > 0 {
        // 如果l1还有节点，就把值加到进位上，然后l1指针后移
        if l1 != nil {
            carry += l1.Val
            l1 = l1.Next // l1：我跑完啦，下一位！
        }
        // 如果l2还有节点，同样操作
        if l2 != nil {
            carry += l2.Val
            l2 = l2.Next // l2：等等我，我也快到终点了！
        }
        
        // 当前位的计算结果是carry的个位数
        current.Next = &ListNode{Val: carry % 10}
        current = current.Next // current：我要去下一个位置啦
        carry /= 10 // 进位更新，只保留十位数（如果有的话）
    }
    
    // 哑节点的下一个节点才是真正的头节点（哑节点：我只是个工具人）
    return dummy.Next
}

3.3 为什么这样高效？​

  • 代码更紧凑：去掉冗余变量，逻辑更清晰
  • 边界处理更优雅：一个循环搞定所有情况，包括不等长链表和最后的进位
  • 性能不变但可读性提升：时间和空间复杂度没变，但代码更像诗一样优美

四、王者进阶：实战中的性能优化​

4.1 避免频繁内存分配​

在Go中，频繁创建小对象会给GC带来压力。可以预先估算结果长度：

// 估算结果长度，避免频繁扩容
maxLen := max(len(l1), len(l2)) + 1 // +1 预留进位空间

4.2 并发安全考量​

在并发场景下，需要对链表操作加锁：

import "sync"

func addTwoNumbersConcurrent(l1, l2 *ListNode) *ListNode {
    var mu sync.Mutex
    // ... 原有逻辑，操作链表时加锁 ...
}

五、算法思维的迁移应用​

两数相加的链表操作思想可以推广到更多场景：

  1. 链表反转：解决正序存储数字相加问题的前置操作
  2. 链表乘法：将一位数乘法拆解为多次加法操作
  3. 大数运算：突破编程语言数值类型限制的通用方案

面试金句：当面试官问你"如何处理超大整数相加？"时，不妨自信回答："用链表实现，就像这道两数相加题一样，每位单独处理，进位依次传递。"

结语：算法优化的本质是优雅​

从青铜到黄金的演进，不仅是代码的优化，更是思维的升华。在云原生时代，这种对细节的打磨尤为重要——就像我们优化微服务的响应时间，每一行代码的精简都可能带来巨大的性能提升。

记住：最好的算法不仅能解决问题，还能让阅读代码的人会心一笑。下一次遇到链表题时，不妨先画个图，再想想今天这两只倒着跑的兔子——算法之美，往往藏在这些生动的比喻里。