题解 | #两个链表生成相加链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
# 简单处理先将链表倒序相加，得到的结果倒序输出
class Solution:
    def addInList(self , head1 , head2 ):
        head1 = self.reverse(head1)
        head2 = self.reverse(head2)
        cur  = self.addTwo(head1, head2)
        return self.reverse(cur)

    def addTwo(self, head1, head2):


        head = ListNode(0)
        cur = head
        carry = 0
        while head1 and head2:

            val = head1.val + head2.val + carry
            if val > 9 :
                val -= 10
                carry = 1
            else:
                carry = 0 
            head1.val = val 
            cur.next = head1
            cur = cur.next 
            head1 = head1.next
            head2 = head2.next

        while head1:
            val = head1.val + carry
            if val > 9:
                val -= 10
                carry = 1
            else:
                carry = 0
            head1.val = val
            cur.next = head1
            cur = cur.next
            head1 = head1.next
        while head2:
            val = head2.val + carry
            if val > 9:
                val -= 10
                carry = 1
            else:
                carry = 0
            head2.val = val
            cur.next = head2
            cur = cur.next
            head2 = head2.next
        if carry == 1:
            cur.next = ListNode(1)
        else:
            cur.next = None
        return head.next

    def addTwoNum(self, head1, head2, carry):

        if head1 is None and head2 is None:
            if carry == 1:
                return ListNode(1)
            else:
                return None
        curCarry = 0
        curVal = carry

        curVal += head1.val if head1 else 0
        curVal += head2.val if head2 else 0
        if curVal > 9:
            curVal -= 10
            curCarry = 1
        if head1 is None:
            head2.val = curVal
            head2.next = self.addTwoNum(head1, head2.next, curCarry)
            return head2
        if head2 is None:
            head1.val = curVal
            head1.next = self.addTwoNum(head1.next, head2, curCarry)
            return head1
        head1.val = curVal
        head1.next = self.addTwoNum(head1.next, head2.next, curCarry)
        return head1

    def reverse(self, head):

        prev = None
        cur = head
        while cur:
            next_ = cur.next
            cur.next = prev
            prev = cur
            cur = next_
        return prev