LeetCode 002 Add Two Numbers

LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].


• 0 <= Node.val <= 9


• It is guaranteed that the list represents a number that does not have leading zeros.

题目大意：

数位链表(从最低位到最高位)相加

算法思路：

类似于merge sort

注意事项：

1. 其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
2. 所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理

Python代码：

def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
	fake_head = ListNode(0)
	carry = 0
	it, it2, it_res = l1, l2, fake_head
	while it or it2:
		value = carry
		if it:
			value += it.val
			it = it.next
		if it2:
			value += it2.val
			it2 = it2.next
		carry = 1 if value >= 10 else 0
		value %= 10
		it_res.next = ListNode(value)
		it_res = it_res.next
	if carry == 1:
		it_res.next = ListNode(1)
	return fake_head.next

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1)