Add Two Numbers

题目描述

You are given two linked lists representing two non-negative numbers. 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.

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

解题方法

code的结构类似Merge two sorted list, 只不过变成了加法还有carry的判断。

• dummy node用来保存头的位置
• pre用来跟随head, 并且如果最后一位是0时删掉最后一个node

注意点

• 最终还剩下的carry还要判断是否为1

Solution

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

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        carry = 0
        head = ListNode(0)
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        while l1 and l2:
            s = l1.val + l2.val + carry
            head.next = ListNode(0)
            if s < 10:
                head.val = s
                carry = 0
            else:
                head.val = s - 10
                carry = 1
            l1 = l1.next
            l2 = l2.next
            head = head.next
            pre = pre.next

        while l1:
            head.next = ListNode(0)
            s = l1.val + carry
            if s < 10:
                head.val = s
                carry = 0
            else:
                head.val = s - 10
                carry = 1
            head = head.next
            l1 = l1.next
            pre = pre.next

        while l2:
            head.next = ListNode(0)
            s = l2.val + carry
            if s < 10:
                head.val = s
                carry = 0
            else:
                head.val = s - 10
                carry = 1
            head = head.next
            l2 = l2.next
            pre = pre.next

        if carry == 1:
            head.val = 1
        else:
            pre.next = None

        return dummy.next

Reference