算法之美_使用链表计算两个非负整数相加

算法复杂度：O(m|n)

实现方式：遍历链表，需要关注进位与链表反转

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

class Solution:

    def reverse(self, l1: ListNode) -> ListNode:

        nextNode = l1.next;

        l1.next = None;

        currNode = l1;

        while (None != nextNode):

            temp = nextNode.next

            nextNode.next = currNode

            currNode = nextNode

            nextNode = temp

        return currNode

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        overFlag = 0;

        firstNode = l1;

        while (l1 != None or l2 != None):

            val1 = (l1.val if (l1 != None) else 0)

            val2 = (l2.val if (l2 != None) else 0)

            val1 = val1 + val2 + overFlag;

            overFlag = 0;

            if (val1 >= 10):

                val1 -= 10;

                overFlag = 1;

            l1.val = val1;

            l1Next= (l1.next if (l1 != None) else None)

            l2 = (l2.next if (l2 != None) else None)

            if ((overFlag > 0 or None != l2) and None == l1Next):

                l1Next = ListNode(0)

                l1.next = l1Next;

            l1 = l1Next;

        return self.reverse(firstNode)