Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Solution

/**
 * 本代码由九章算法编辑提供。版权所有，转发请注明出处。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，Big Data 项目实战班，
 * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
 */

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param l1: the first list
    # @param l2: the second list
    # @return: the sum list of l1 and l2 
    def addLists2(self, l1, l2):
        # write your code here
        l1 = self.reverse(l1);
        l2 = self.reverse(l2);
        sum = ListNode(0)
        cur = sum
        pre = sum
        while l1!=None and l2!=None:
            cur.val += l1.val+l2.val
            cur.next = ListNode(cur.val/10)
            cur.val = cur.val%10
            l1 = l1.next
            l2 = l2.next
            pre = cur
            cur = cur.next
        while l1!=None:
            cur.val += l1.val
            cur.next = ListNode(cur.val/10)
            cur.val = cur.val%10
            l1 = l1.next
            pre = cur
            cur = cur.next
        while l2!=None:
            cur.val += l2.val
            cur.next = ListNode(cur.val/10)
            cur.val = cur.val%10
            l2 = l2.next
            pre = cur
            cur = cur.next
        if cur.val==0:
            pre.next = None
        return self.reverse(sum)

    def reverse(self, head):
        # write your code here
        curr = None
        next = head
        while next:
            prev = curr
            curr = next
            next = next.next
            curr.next = prev
        return curr