2. 两数相加

mid

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解

将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 00
- 比如 987 + 23 = 987 + 023 = 1010
每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
如果两个链表全部遍历完毕后，若有进位制，则在新链表最前方添加包含进位制的节点

时间复杂度 O(n)，空间复杂度 O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        up = 0  # 进位
        node = ListNode()
        head = node  # 记录头结点的位置
        while True:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            _sum = val1+val2+up
            up = _sum//10 % 10  # 取十位为进位
            add = _sum % 10  # 取个位
            node.val = add

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

            if not l1 and not l2:
                if up > 0:
                    node.next = ListNode(val=up)
                break
            next = ListNode()
            node.next = next
            node = next
        return head

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    up := 0
	node := &ListNode{}
	head := node
	var val1, val2 int
	for {
		if l1 != nil {
			val1 = l1.Val
		} else {
			val1 = 0
		}

		if l2 != nil {
			val2 = l2.Val
		} else {
			val2 = 0
		}

		sum := val1 + val2 + up
		up = sum / 10 % 10
		add := sum % 10

		node.Val = add

		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}

		if l1 == nil && l2 == nil {
			if up > 0 {
				node.Next = &ListNode{Val: up}
			}
			break
		}
        node.Next=&ListNode{}
        node =node.Next
	}
	return head
}