链表相加(一)

# -*- coding: utf-8 -*-


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


class LinkedList:
    def __init__(self):
        self.head = None

    def initLinkedList(self, nums):
        n = len(nums)

        if n > 0:
            self.head = ListNode(nums[0])
            cur = self.head
            for i in range(1, n):
                cur.next = ListNode(nums[i])
                cur = cur.next

        return self.head

    @staticmethod
    def printLinkedList(head):
        if not head:
            return []

        cur, res = head, []
        while cur:
            res.append(cur.val)
            cur = cur.next
        return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param l1 ListNode类
# @param l2 ListNode类
# @return ListNode类
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/521d83306d964c1188639033eb59621d?tpId=196&tqId=40273&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        从前往后，遍历链表l1和l2，对于第i项相加和sum = h1.val + h2.val + carry，新建节点ListNode(sum % 10), 记录进位carry = sum / 10
    复杂度：
        时间复杂度：O(min(M, N) ~ max(M, N))
        空间复杂度：O(1)
    """

    def ListAdd(self, l1, l2):
        # write code here
        if not l1:
            return l2
        elif not l2:
            return l1

        head1, head2, carry = l1, l2, 0
        dummy = ListNode(-1)
        cur = dummy

        while head1 and head2:
            sum = head1.val + head2.val + carry
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head1 = head1.next
            head2 = head2.next
            cur = cur.next

        while head1:
            if carry == 0:
                cur.next = head1
                break
            sum = carry + head1.val
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head1 = head1.next
            cur = cur.next

        while head2:
            if carry == 0:
                cur.next = head2
                break
            sum = carry + head2.val
            cur.next = ListNode(sum % 10)
            carry = sum / 10
            head2 = head2.next
            cur = cur.next

        if carry: # 链表遍历结束，仍有进位，如1 + 9
            cur.next = ListNode(carry)

        return dummy.next


if __name__ == "__main__":
    sol = Solution()

    # nums1, nums2 = [2, 5, 6], [5, 6, 1]

    # nums1, nums2 = [0], [1, 2, 3, 4, 5, 6]

    nums1, nums2 = [9, 9, 9], [9, 9, 0]

    # nums1, nums2 = [7, 5, 3, 5, 6, 2, 9, 1], [2, 7, 0, 9, 3, 6]

    # nums1, nums2 = [9, 9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9, 9, 9]

    l = LinkedList()
    l1, l2 = l.initLinkedList(nums1), l.initLinkedList(nums2)
    # print LinkedList.printLinkedList(l1), LinkedList.printLinkedList(l2)

    res = sol.ListAdd(l1, l2)
    print l.printLinkedList(res)



# python2直接超时 无语的效率