0002._add_two_numbers.md

Links:

1. https://leetcode.com/problems/add-two-numbers/
2. https://leetcode-cn.com/problems/add-two-numbers/

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

Tags

1. 数学
2. 链表

Solution1

将链表转换为字符串，再转换为数字相加。再用相加的结果构建新的链表。

PS:

1. 构建新链表的过程中多次逆序。
2. 注意Corner cases。

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # coner cases
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        list1 = []
        list2 = []

        # list -> str -> int -> sum
        while l1:
            list1.append(l1.val)
            l1 = l1.next
        while l2:
            list2.append(l2.val)
            l2 = l2.next

        str1 = ''.join([str(i) for i in list1[::-1]])
        str2 = ''.join([str(i) for i in list2[::-1]])

        total = str(int(str1) + int(str2))
        total = total[::-1]

        # build new linked_list with sum
        head = ListNode(int(total[0]))
        cursor = head
        for i in range(1, len(total)):
            cursor.next = ListNode(int(total[i]))
            cursor = cursor.next

        return head

Solution2:

1. 设置进位carry。
2. 遍历两个链表，每次算一位：carry, val = divmod(num1 + num2 + carry, 10)。
3. 用val构建新的链表节点：ListNode(val)。

Python:

class Solution:
    def addTwoNumbers(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        carry = 0
        dummy_head = cursor = ListNode(0)

        while l1 or l2 or carry:  # 链表l1, l2遍历完后，仍要考虑前一次求和是否有进位。
            num1 = num2 = 0
            if l1:
                num1 = l1.val
                l1 = l1.next
            if l2:
                num2 = l2.val
                l2 = l2.next

            carry, val = divmod(num1 + num2 + carry, 10)
            cursor.next = ListNode(val)
            cursor = cursor.next

        return dummy_head.next

Go:

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummyHead := &ListNode{Val: 0}
	carry, current := 0, dummyHead

	for l1 != nil || l2 != nil || carry != 0 {
		n1, n2 := 0, 0

		if l1 != nil {
			n1 = l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}

		current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
		current = current.Next
		carry = (n1 + n2 + carry) / 10
	}
	return dummyHead.Next
}

Solution3:

1. 类似Solution2。每次算一位。
2. 但是用递归的方法。

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        if l1.val + l2.val < 10:
            l3 = ListNode(l1.val + l2.val)
            l3.next = self.addTwoNumbers(l1.next, l2.next)
        else:
            carry = 1
            l3 = ListNode(l1.val + l2.val - 10)
            l3.next = self.addTwoNumbers(l1.next, self.addTwoNumbers(l2.next, ListNode(carry)))

        return l3