# Leetcode题库第２题：两数相加 用Julia怎么解？

fix：上一版 `==` 实现的有 bug，又加了几个测试
update: 加了点 `addTwoNumbers` 的测试。用的时候看情况把测试数量调小一点，不然一堆报错。

``````using Test
import Base: (+), (==)

abstract type ListNode end
mutable struct Node <: ListNode
val::UInt8 #再小就要手动处理 bit 流
next::ListNode
end

# List Node Null
struct Null <: ListNode end
# const null = LnNull()
null = Null()
==(::Null, ::Null) = true
==(::Null, ::Node) = false
==(::Node, ::Null) = false
# 可变数据结构不能使用 == 直接比较
function ==(ln1::Node, ln2::Node)
ln1.val  != ln2.val  && return false
ln1.next != ln2.next && return false
true
end

# 在此作答
end
# 重载 +, 便于使用
# 可以直接写 `Node(0) + Node(1)`
# 而不是每次都要调用函数

#= 辅助函数（答题非必须）
=#
"数字转数组"
function num2arr(n::Integer)
## 1- digits 法
# digits 输出为倒序
#   digits(123) == [3, 2, 1]
n |> digits |> reverse

## 2-string 法
# s = string(n)
# a = []
# for c in s
#     push!(a, parse(UInt8, c))
# end
# a
end
function num2ln(n::Integer)
arr = num2arr(n)
ln = null
for i in arr
ln = Node(UInt8(i), ln)
end
ln
end
Node(n::Integer) = num2ln(n)
Node() = null

# 单元测试
@testset "Node" begin
# not equal
@test Node()  != Node(1)
@test Node(1) != Node()
@test Node(1) != Node(2)
@test Node(2) != Node(1)
@test Node(10) != Node(0)
@test Node(123456) != Node(123455)
@test BigInt(123456789) |> Node != null

# null
@test Node() == Null()
@test Node() == null

# Int64
@test Node(0) == Node(0x00, Null())
@test Node(1) == Node(0x01, Null())
@test 1234 |> Node ==
Node(0x04, Node(0x03, Node(0x02, Node(0x01, Null()))))

# Unsigned
@test 0xFF |> Node ==
Node(0x05, Node(0x05, Node(0x02, Null())))
@test 0xFFFF |> Node ==
Node(0x05, Node(0x03, Node(0x05, Node(0x05, Node(0x06, Null())))))

# BigInt
@test BigInt(123456789) |> Node ==
Node(0x09, Node(0x08, Node(0x07, Node(0x06, Node(0x05, Node(0x04, Node(0x03, Node(0x02, Node(0x01, Null())))))))))
end

@test Node(0) + Node(0) == Node(0)
@test Node(1) + Node(9) == Node(10)

@test Node(10) + Node(0) == Node(10)
@test Node(123) + Node(0) == Node(123)
@test Node(511) + Node(513) == Node(1024)

@test Node(9) + Node(9) == Node(2*9)

i=2^4
@test Node(i) + Node(i) == Node(2*i)

for i=1:2^8+1
@test Node(i) + Node(0) == Node(i)
@test Node(0) + Node(i) == Node(i)
@test Node(i) + Node(i) == Node(2*i)
@test Node(i+1) + Node(i-1) == Node(2*i)
end
end
``````
1赞

``````using BenchmarkTools
import Base: (+), (==)

abstract type ListNode end
mutable struct Node <: ListNode
val::UInt8 #再小就要手动处理 bit 流
next::ListNode
end

# List Node Null
struct Null <: ListNode end
# const null = LnNull()
null = Null()
==(::Null, ::Null) = true
==(::Null, ::Node) = false
==(::Node, ::Null) = false
# 可变数据结构不能使用 == 直接比较
function ==(ln1::Node, ln2::Node)
ln1.val  != ln2.val  && return false
ln1.next != ln2.next && return false
true
end

# 节点相加，带进位，忽略 next
val_sum = val1 + val2 + carry
new_val = val_sum % 10 # 只保留 1 位数
carry   = val_sum ÷ 10  # 是否有进位

new_val, carry
end
addNodesVal(::Null,   ::Null, c::Bool) = (UInt8(c), 1)

ln3 = Node(val, null)
next_node = ln3

while carry==1 || ln1.next!=null || ln2.next!=null
_val, carry = addNodesVal(ln1.next, ln2.next, carry)
next_node.next = Node(_val, null)

# 下一圈初始化
ln1.next!=null && (ln1 = ln1.next)
ln2.next!=null && (ln2 = ln2.next)
next_node = next_node.next
end

ln3
end

# [两数相加 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/)
root_node = Node(0xff, null)
cur_node = root_node
carry = 0

while ln1!=null || ln2!=null
v1 = ln1!=null ? ln1.val : 0
v2 = ln2!=null ? ln2.val : 0

temp = v1 + v2 + carry
carry = temp ÷ 10 # 整除

cur_node.next = Node(temp%10, null)
cur_node = cur_node.next

ln1!=null && (ln1 = ln1.next)
ln2!=null && (ln2 = ln2.next)
end
if carry > 0
cur_node.next = Node(a, null)
end
root_node.next
end

root_node = Node(0xff, null)
cur_node = root_node
carry = 0
sum = 0

while ln1!=null || ln2!=null
sum = carry
ln1!=null && (sum += ln1.val)
ln2!=null && (sum += ln2.val)

if sum >= 10
carry = sum ÷ 10
sum %= 10
else
carry = 0
end

cur_node.next = Node(sum, null)
cur_node = cur_node.next

ln1!=null && (ln1 = ln1.next)
ln2!=null && (ln2 = ln2.next)
end
if carry > 0
cur_node.next = Node(a, null)
end
root_node.next
end

# - [使用伪头节点，对应位依次相加，记录进位 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/shi-yong-wei-tou-jie-dian-dui-ying-wei-yi-ci-xiang/ )
root_node = Node(0xff, null)
cur_node = root_node
carry = 0
sum = 0

while ln1!=null || ln2!=null || carry>0
sum = carry
ln1!=null && (sum += ln1.val)
ln2!=null && (sum += ln2.val)
carry = sum ÷ 10

cur_node.next = Node(sum%10, null)
cur_node = cur_node.next

ln1!=null && (ln1 = ln1.next)
ln2!=null && (ln2 = ln2.next)
end
if carry > 0
cur_node.next = Node(a, null)
end
root_node.next
end

# [最简写法 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/zui-jian-xie-fa-by-baal-3/)
root_node = Node(0xff, null)
cur_node = root_node
carry = 0

while ln1!=null || ln2!=null || carry>0
cur_node.next = Node(0, null)
cur_node = cur_node.next

ln1 = ln1!=null ? (carry+=ln1.val; ln1.next) : ln1
ln2 = ln2!=null ? (carry+=ln2.val; ln2.next) : ln2

cur_node.val = carry % 10
carry = carry ÷ 10
end
root_node.next
end

ln3
end
if ln1==null && ln2==null && carry==0
return null, 0
end

ln1 = ln1!=null ? (carry+=ln1.val; ln1.next) : ln1
ln2 = ln2!=null ? (carry+=ln2.val; ln2.next) : ln2

cur_node = Node(carry%10, null)
carry = carry ÷ 10

next, carry = addTwoNumbers_Baal2_rec(ln1, ln2, carry)
cur_node.next = next

cur_node, carry
end

#= 辅助函数
=#
"数字转数组"
function num2arr(n::Integer)
## 1- digits 法
# digits 输出为倒序
#   digits(123) == [3, 2, 1]
n |> digits |> reverse
end
function num2ln(n::Integer)
arr = num2arr(n)
ln = null
for i in arr
ln = Node(UInt8(i), ln)
end
ln
end
Node(n::Integer) = num2ln(n)
Node() = null

# test
big_num = big"1122334455667788990998877665544332211"
result_big_num = big_num*2
big_node = Node(big_num)
result_node = Node(result_big_num)

# @btime \$big_num + \$big_num

``````
``````addTwoNumbers_wo2(big_node, big_node) == result_node = true
15.700 μs (37 allocations: 1.16 KiB)
addTwoNumbers_leetcode(big_node, big_node) == result_node = true
18.799 μs (38 allocations: 1.19 KiB)
addTwoNumbers_coderscat(big_node, big_node) == result_node = true
19.500 μs (38 allocations: 1.19 KiB)
addTwoNumbers_brooot(big_node, big_node) == result_node = true
19.999 μs (38 allocations: 1.19 KiB)
addTwoNumbers_Baal(big_node, big_node) == result_node = true
20.699 μs (38 allocations: 1.19 KiB)
addTwoNumbers_Baal2(big_node, big_node) == result_node = true
13.299 μs (75 allocations: 2.33 KiB)
``````