leetcode 2: 两数相加 | 浮生无事Blog

题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法

// 时间复杂度 O(max(m,n)) 空间复杂度 O(max(m,n))
// 说明: 从个位数(链表第一个节点)开始，依次求和 sum, 若sum>9, 则记录进位appendVal, 与下一次求和结果sum + appendVal
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
	var l3 ListNode
	p := &l3
	appendVal := 0
	for l1 != nil || l2 != nil {
		sum := 0
		if l1 != nil && l2 != nil {
			sum = l1.Val + l2.Val
			l1 = l1.Next
			l2 = l2.Next
		} else if l1 != nil && l2 == nil {
			sum = l1.Val
			l1 = l1.Next
		} else if l1 == nil && l2 != nil {
			sum = l2.Val
			l2 = l2.Next
		}
		sum = sum + appendVal
		appendVal = sum / 10
		p.Val = sum % 10
		
		// 两个链表都已遍历完，且最后一次同位求和无进位时，当前节点，即为结果链表最后一个节点，否则，需要追加一个 Val=appendVal 的节点
		if l1 == nil && l2 == nil {
			if appendVal > 0 {
				p.Next = &ListNode{Val: appendVal, Next: nil}
			} else {
				p.Next = nil
			}
		} else {
			p.Next = &ListNode{Val: 0, Next: nil}
			p = p.Next
		}
	}
	return &l3
}

代码优化

// 时间复杂度 O(max(m,n)) 空间复杂度 O(max(m,n))
// 说明: 从个位数(链表第一个节点)开始，依次求和 sum, 若sum>9, 则记录进位appendVal, 与下一次求和结果sum + appendVal
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
	var l3 ListNode
	p := &l3
	appendVal := 0
	for l1 != nil || l2 != nil {
		sum := 0
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		sum = sum + appendVal

		appendVal = sum / 10

		p.Val = sum % 10

		// 两个链表都已遍历完，且最后一次同位求和无进位时，当前节点，即为结果链表最后一个节点，否则，需要追加一个 Val=appendVal 的节点
		if l1 == nil && l2 == nil && appendVal == 0 {
			p.Next = nil
		} else {
			p.Next = &ListNode{Val: appendVal, Next: nil}
			p = p.Next
		}
	}

	return &l3
}