LeetCode【链表】2. 两数相加 LeetCode刷题

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

单纯的链表题目，因为是倒序着的，所以只需要从头开始遍历相加就可以，【2 -> 4 -> 3，5 -> 6 -> 4 】从2和5开始相加，如果有进位就加到后面一位的相加中。要考虑的是当链表长度不相同的时候，【2 -> 4 -> 3，5 -> 6】这个时候最后一位就要单独判断一下。

class ListNode(object): def __init__(self, x): self.val = x self.next = Noneclass Solution(object):def addTwoNumbers(self, l1, l2):head = None # 链表头 tail = None # 链表尾部，方便插入的时候不需要遍历 carry = 0 while l1 or l2: l1_v = l1.val if l1 else 0 l2_v = l2.val if l2 else 0 val = l1_v + l2_v + carry carry = val // 10 val = val % 10node = ListNode(val) if not head: head = node tail = head else: tail.next = node tail = node if l1: l1 = l1.next if l2: l2 = l2.nextif carry>0: tail.next = ListNode(1) return head''''''''''' 测试使用 ''''''''''''''' def get_list(arr): l1 = ListNode(arr[0]) head = l1 for i in range(1,len(arr)): tmp = ListNode(arr[i]) l1.next=tmp l1=tmp return head def print_linked(l1): while l1: print(l1.val,end='') l1=l1.next if __name__ == '__main__': l1 = get_list([2,4,3]) l2 = get_list([5,6,4]) s = Solution() r = s.addTwoNumbers(l1,l2) print_linked(r) print('708') print("---------------") l1 = get_list([8,1,7]) l2 = get_list([3,2]) s = Solution() r = s.addTwoNumbers(l1, l2) print_linked(r) print('147')print("---------------") l1 = get_list([8, 2]) l2 = get_list([0]) s = Solution() r = s.addTwoNumbers(l1, l2) print_linked(r) print('82')

【LeetCode【链表】2. 两数相加】