刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/add-two-numbers-ii/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

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

提示：

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能翻转该如何解决？

思路

思路对比

这道题有两种思路

• 翻转链表
• 栈

用栈会符合进阶的要求，而且容易想到，毕竟栈其实是最熟悉的数据结构之一了。
但是栈方法无论是时间、空间上，都相比于翻转链表没有优势，空间上甚至是劣势

所以感觉没啥意思，这个进阶要求有点搞笑了

思路拆解

以翻转链表为例，其实就是三个步骤

• 翻转两个链表
• 链表求和
• 翻转结果链表

如果要求不改变原参数的结构，那就加和时不用使用原本的链表节点，并且返回前再把参数翻转回去即可。

没什么好说的了，上代码，细节在注释了～

代码

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 特殊情况可以直接返回了
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	}
	// 翻转链表1
	l1r := reverseList(l1)
	// 翻转链表2
	l2r := reverseList(l2)
	// 链表遍历求和
	sumList := addList(l1r, l2r)
	// 翻转结果列表
	return reverseList(sumList)
}

func addList(l1, l2 *ListNode) *ListNode {
	veryHead := &ListNode{}
	head := veryHead
	c := 0
    // 这里是直接用的原本的节点，可以节约空间
    // 不动原本结构那就直接新建节点即可
	for l1 != nil && l2 != nil {
		sum := l1.Val + l2.Val + c
		if sum >= 10 {
			sum -= 10
			c = 1
		} else {
			c = 0
		}
		l1.Val = sum
		head.Next = l1
		head = head.Next
		l1 = l1.Next
		l2 = l2.Next
	}

    // 这俩个for都是为了直接用的原本的节点产生的复杂度
    // 不用原本节点，所有逻辑都合并到上面的一个for里即可
	for l2 != nil {
		sum := l2.Val + c
		if sum >= 10 {
			sum -= 10
			c = 1
		} else {
			c = 0
		}
		l2.Val = sum
		head.Next = l2
		head = head.Next
		l2 = l2.Next
	}

	for l1 != nil {
		sum := l1.Val + c
		if sum >= 10 {
			sum -= 10
			c = 1
		} else {
			c = 0
		}
		l1.Val = sum
		head.Next = l1
		head = head.Next
		l1 = l1.Next
	}
    // 别忘了最后可能有一个单独的进位
	if c == 1 {
		head.Next = &ListNode{Val: 1}
	}
	return veryHead.Next
}

// 迭代方式翻转链表
func reverseList(head *ListNode) *ListNode {
	var pre, next *ListNode
	now := head
	for now != nil {
		next = now.Next
		now.Next = pre
		pre = now
		now = next
	}
	return pre
}