1-链表-两数相加

这是链表篇章的第一篇，从现在开始要玩链表了。力扣链接。

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

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

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

这道题看起来很好玩，其实就是链表的头部为数字的最低位，让两个链表组成两个数相加，然后生成新的链表。

这道题老规矩可以玩玩暴力法，将两个链表变成数字然后相加。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	left, right := calculateNumber(l1), calculateNumber(l2)
	sum := left + right
	result := &ListNode{
		Val: sum % 10,
	}
	sum /= 10
	last := result
	for sum != 0 {
		last.Next = &ListNode{
			Val: sum % 10,
		}
		sum /= 10
		last = last.Next
	}
	return result
}

func calculateNumber(n *ListNode) int {
	result, level := 0, 1
	for n != nil {
		result = result + n.Val*level
		level *= 10
		n = n.Next
	}
	return result
}

?代码虽然写好了，但是测试用例没过：

显然，这里越界了。 换了一下big.Int，还是越界，好的 放弃暴力方法了：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	left, right := calculateNumber(l1), calculateNumber(l2)
	sum := big.NewInt(0).Add(left, right)
	result := &ListNode{
		Val: int(sum.Int64() % 10),
	}
	sum = big.NewInt(0).Div(sum, big.NewInt(10))
	last := result
	for sum.Sign() != 0 {
		last.Next = &ListNode{
			Val: int(sum.Int64() % 10),
		}
		sum = big.NewInt(0).Div(sum, big.NewInt(10))
		last = last.Next
	}
	return result
}

func calculateNumber(n *ListNode) *big.Int {
	result := big.NewInt(0)
	level := big.NewInt(1)

	for n != nil {
		val := big.NewInt(int64(n.Val))
		val.Mul(val, level)
		result.Add(result, val)
		level.Mul(level, big.NewInt(10))
		n = n.Next
	}
	return result
}

既然不暴力了，那就尝试一下双指针，其实就是模拟法，一个一个加，加完为止。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	in := 0
	result := &ListNode{Next: nil}
	cur := result
	for l1 != nil || l2 != nil {
		left := 0
		if l1 != nil {
			left = l1.Val
			l1 = l1.Next
		}
		right := 0
		if l2 != nil {
			right = l2.Val
			l2 = l2.Next
		}
		sum := left + right + in
		cur.Next = &ListNode{
			Val: sum % 10,
		}
		cur = cur.Next
		in = sum / 10
	}
	if in != 0 {
		cur.Next = &ListNode{Val: in}
	}
	return result.Next
}