leet code 两数相加

题目

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

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

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

1，读取每个链表元素到列表中（逆序翻转，方便求和）
使用while循环读取每个节点，并使用列表insert方法插入，直接实现顺序调整
2，对两个列表中元素组成的整数求和
先把列表中每个元素整合为一个字符串，然后使用int转换为整数
（可以尝试整数直接*10相加）
3，将和逆序到列表中
把整数转换为字符串，然后逐个转换为int放到列表中
4，由列表生成链表
这个是难点，开始没有想到，需要设计一个哑点
再把哑点赋值给当前节点，切记不可对哑点直接操作
最后返回哑点的下一个节点

# 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
        """
        l1 = self.get_vals(l1)
        l2 = self.get_vals(l2)
        l1_num = self.tran_list_to_int(l1)
        l2_num = self.tran_list_to_int(l2)
        l_sum = l1_num + l2_num
        result_list = self.tran_int_to_list(l_sum)
        
        dummyHead = ListNode(0)
        curr = dummyHead
        for i in result_list:
            curr.next = ListNode(i)
            curr = curr.next
        return dummyHead.next
    
    def get_vals(self, l):
        l_val = []
        l_val.append(l.val)
        next = l.next
        while next:
            l_val.insert(0, next.val)
            next = next.next
        return l_val
            
    def tran_list_to_int(self, l):
        l_str = ''
        for i in range(len(l)):
            l_str += str(l[i])
        return int(l_str)
    
    def tran_int_to_list(self, num):
        l = []
        s_num = str(num)
        for i in s_num:
            l.insert(0, int(i))
        return l

解法二

使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

遍历完两个列表中所有元素

位数不一样的情况下，已经结束列表对应位用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
        """
        dummyNode = ListNode(0)
        curr = dummyNode
        p1 = l1
        p2 = l2
        carry = 0
        while p1 or p2:
            x = p1.val if p1 else 0
            y = p2.val if p2 else 0
            c_sum = x + y + carry
            carry = c_sum/10
            curr.next = ListNode(c_sum%10)
            curr = curr.next
            if p1:
                p1 = p1.next if p1.next else None
            if p2:
                p2 = p2.next if p2.next else None

        if carry > 0:
            curr.next = ListNode(carry)
        return dummyNode.next

最后编辑于：2019.08.04 11:19:32