leetcode-hot-(2/100)

zhangshaos · · 950 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

2/100-两数相加

题目描述

image.png

go to leetcode

分析解答

从题目描述中,联想到CPU的加法器:每个链表代表一个数字,每个节点则表示一位数字。
因此,我们可以模拟CPU,也设立一个进位标志位carry
对于合并后的新节点,节点的值value = 对应位置两个节点的value和 + carry

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 1.for each reverse-list l1, l2:
    //      new node's val = l1.val + l2.val + carry(初值为0)
    //      carry = new carry
    // 2.handle left reverse-list
    var (
        head, tail *ListNode
        carry = 0
    )
    p1, p2 := l1, l2
    for p1 != nil && p2 != nil {
        if head == nil {
            tail = new(ListNode)
            head = tail
        } else {
            tail.Next = new(ListNode)
            tail = tail.Next
        }
        sum := p1.Val + p2.Val + carry
        tail.Val = sum % 10
        carry = sum / 10
        p1 = p1.Next
        p2 = p2.Next
    }
    for p1 != nil {
        tail.Next = new(ListNode)
        tail = tail.Next
        sum := p1.Val + carry
        tail.Val = sum % 10
        carry = sum / 10
        p1 = p1.Next
    }
    for p2 != nil {
        tail.Next = new(ListNode)
        tail = tail.Next
        sum := p2.Val + carry
        tail.Val = sum % 10
        carry = sum / 10
        p2 = p2.Next
    }
    if carry != 0 {
        tail.Next = new(ListNode)
        tail = tail.Next
        tail.Val = carry
        carry = 0
    }
    return head
}

反思

进位的思想可以推广到其他有限容量的操作上。
例如B+树的分裂:
后续遍历,插入节点,“计算进位”,然后对父节点同样处理进位


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:zhangshaos

查看原文:leetcode-hot-(2/100)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

950 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传