两数相加

aside section._1OhGeD · · 1301 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

两数相加

题目

来自： https://leetcode-cn.com/problems/add-two-numbers/

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

Go编程实现

思路：迭代计算每位数字的和，记录进位。当全部数位和进位计算完毕，结果得到。

代码如下：

// 单向链表结构
type ListNode struct {
    Val  int
    Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    //判断是否存在操作数为 0 的特例
    if l1.Val == 0 && l1.Next == nil {
        return l2
    }
    if l2.Val == 0 && l2.Next == nil {
        return l1
    }

    result := &ListNode{}
    //迭代处理的结果节点，从第一个开始
    node := result
    // 进位
    var carry int
    // 和
    v := 0
    for {
        // 若 l1 还有，则累加，同时切换下一个l1
        if l1 != nil {
            v += l1.Val
            l1 = l1.Next
        }
        // 若 l2 还有，则累加，同时切换下一个 l2
        if l2 != nil {
            v += l2.Val
            l2 = l2.Next
        }
        //累加进位
        v += carry
        carry = v / 10 // 进位
        node.Val = v % 10 // 当前位
        // 若 l1 l2 进位都没了，结束
        if l1 == nil && l2 == nil && carry == 0 {
            break
        }
        // 构建下一个结果节点
        node.Next = &ListNode{}
        node = node.Next
        v = 0
    }

    return result
}

本实现在 LeetCode 上测试通过，结果为：

执行用时 : 8 ms , 在所有 golang 提交中击败了 96.84% 的用户。

内存消耗 : 4.9 MB , 在所有 golang 提交中击败了 94.01% 的用户。