Python - 两数相加 (有链表无链表)

一.引言

给定两个非空的列表，表示两个非负的整数。它们每位数字都是按照顺序的方式存储的，并且每个节点只能存储一位数字。请将两个数相加并返回结果。

Tips: 两个数字均不会以0为开头

示例:

nums1 = [1,2,3]

nums2 = [2,3,4]

add(nums1, nums2) = 123 + 234 = 357

二.常规解法

常规解法为正常四则运算，主要分4步:

(1) 旋转数组，并获取较长和较短的数组

(2) 计算公共部分的求和，如果 sum = value1 + value2 + add > 10 (字符串长度是否 > 1) ，则进位 add = 1，此处用变量 add 记录进位的大小，不进位时 add = 0

(3) 计算多出来的一部分，因为这一部分和短的没有公共部分，所以计算 value + add 是否大于10 并更新 add 即可

(4) 将 result 翻转得到最终结果

def add_num(_num1, _num2):
    _l1 = len(_num1)
    _l2 = len(_num2)
    # 翻转数组从最小位置开始相加
    _num1.reverse()
    _num2.reverse()
    # 根据长度判断大的数字和小的数字
    if _l1 >= _l2:
        long, short = _num1, _num2
    else:
        long, short = _num2, _num1
    # re 存储结果 add 存储进位
    re = []
    add = 0
    # 计算公共部分和
    for i in range(min(_l1, _l2)):
        value1 = _num1[i]
        value2 = _num2[i]
        add_re = str(value1 + value2 + add)
        # 计算进位
        if len(add_re) > 1:
            add = 1
        else:
            add = 0
        # 增加结果
        re.append(add_re[-1:])
    # 计算较长部分的和
    for j in range(min(_l1, _l2), max(_l1, _l2)):
        value = long[j]
        add_re = str(value + add)
        # 计算进位
        if len(add_re) > 1:
            add = 1
        else:
            add = 0
        # 增加结果
        re.append(add_re[-1:])
    re.reverse()
    return ''.join(re)

num1 = [1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 7, 8]
num2 = [2, 3, 4, 5, 6, 7, 6, 7, 8, 8, 9, 9, 9, 9, 9, 9]
result = add_num(num1, num2)
print(result)

三.链表解法

链表的解法与上面思路相似，只不过长短数组分段处理变成了两个链表同时处理，逐个遍历时只需要关系另一个链表的 node 是否有值，都有值时代表计算两者公共部分，只有一个链表 node 有值时则计算较长的部分。 node.val 记录当前值， node.next.val 记录下一个值，如果 l1.val + l2.val 大于10则进位，进位无需使用 add 变量记录，而是直接加给对应的 next_val ，依次类推。

1.辅助函数

ListNode 为链表对应的数据结构， initList 将列表转换为 ListNode，convert_list 将链表转换为列表并最终转换为计算结果

# 构造链表
class ListNode:
    def __init__(self, _val=0, _next=None):
        self.val = _val
        self.next = _next


# 初始化链表
def initList(data):
    head = ListNode(data[0])
    r = head
    p = head
    for i in data[1:]:
        node = ListNode(i)
        p.next = node
        p = p.next
    return r


#  链表转化为数组
def convert_list(head):
    ret = []
    if head is None:
        return
    node = head
    while node is not None:
        ret.append(node.val)
        node = node.next
    ret.reverse()
    return ''.join(list(map(lambda x: str(x), ret)))

2.求和主函数

判断 node 是否为 None，当前位置如果和 > 10，保留 value-10 的个位，然后进1位(next.val + 1)

def addTwoNumbers(_l1: ListNode, _l2: ListNode) -> ListNode:
    lrr = _l1
    while True:
        _l1.val = _l1.val + _l2.val
        if _l1.next is None and _l2.next is None and _l1.val < 10:
            break
        if _l1.next is None:
            _l1.next = ListNode(0)
        if _l2.next is None:
            _l2.next = ListNode(0)
        # 进位
        if _l1.val >= 10:
            _l1.val = _l1.val - 10
            _l1.next.val += 1
        _l1 = _l1.next
        _l2 = _l2.next
    return lrr

num1 = [1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 7, 8]
num2 = [2, 3, 4, 5, 6, 7, 6, 7, 8, 8, 9, 9, 9, 9, 9, 9]
l1 = initList(num1)
l2 = initList(num2)
print(convert_list(addTwoNumbers(l1, l2)))

3.时间比较

num1 = [1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 7, 8]
num2 = [2, 3, 4, 5, 6, 7, 6, 7, 8, 8, 9, 9, 9, 9, 9, 9]
st = time.time()
result = add_num(num1, num2)
print(result)
end1 = time.time()
l1 = initList(num1)
l2 = initList(num2)
print(convert_list(addTwoNumbers(l1, l2)))
end2 = time.time()
print(123452345678 + 2345676788999999)
end3 = time.time()
print((end1 - st), (end2 - end1), (end3 - end2))

基础解法和链表解法时间消耗相近，整体慢自带加法一个数量级。

2345800241345677
2345800241345677
2345800241345677
1.7881393432617188e-05 1.8835067749023438e-05 1.1920928955078125e-06