问题描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

使用递归实现，依次取出链表第一个节点相加求和。若其中一个链表为空，另一个链表不为空，则空链表用值为0的节点代替，直至两个链表都为空结束递归。

Python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    
    def __init__(self):
    	# 保留进位信息
        self.a = 0
        
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        if l1 == None and l2 == None:
            if self.a > 0:
                return ListNode(self.a)
            else:
                return None
            
        if l1 == None:
            l1 = ListNode()
        if l2 == None:
            l2 = ListNode()

        res = (l1.val+l2.val+self.a)%10
        self.a = (l1.val+l2.val+self.a)//10
        return ListNode(res,self.addTwoNumbers(l1.next,l2.next))