1-链表-两数相加

2023-12-28 12:54:44

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

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

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

你可以假设除了数字 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
}

文章来源:https://blog.csdn.net/weixin_56270372/article/details/135264118
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。