leetcode | 2.两数相加

2.两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

题目链接

思路

对应位置元素带进位相加

代码

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        对应位置元素带进位相加
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        extra = 0
        root = n = ListNode(0)
        while l1 or l2 or extra:
            v1 = v2 = 0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2 = l2.next
            extra, val = divmod(v1 + v2 + extra, 10)
            n.next = ListNode(val)
            n = n.next
        return root.next

    def create_linked_list(self, num):
        link_list = ListNode(num % 10)
        r = link_list
        while num >= 10:
            num = num // 10
            node = ListNode(num % 10)
            r.next = node
            r = r.next
        r.next = None
        return link_list

    def len_list(self, link_list):
        count = 0
        p = link_list
        while p is not None:
            count += 1
            p = p.next

        return count

class Solution1:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        将两个链表分别转化为一个整数,然后将两个整数相加,将结果的逆序构建成一个单链表
  
        t = 1
        res1 = 0

        while l1 is not None:
            res1 += l1.val * t
            t *= 10
            l1 = l1.next

        t = 1
        res2 = 0
        while l2 is not None:
            res2 += l2.val * t
            t *= 10
            l2 = l2.next

        res = res1 + res2
        print(res)

        res_list = ListNode(res % 10)
        r = res_list
        while res >= 10:
            res //= 10
            node = ListNode(res % 10)
            r.next = node
            r = node
        r.next = None

        return res_list

if __name__ == '__main__':
    slt = Solution()
    l1 = slt.create_linked_list(342)
    l2 = slt.create_linked_list(465)
    res = slt.addTwoNumbers1(l1, l2)

    while res is not None:
        print(res.val)
        res = res.next

    print(slt.len_list(l1))