LeetCode第二题: 两数相加
题目描述
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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]
解题思路 - 迭代法
我们可以遍历两个链表，模拟数字相加的过程。需要注意的是，如果两个链表的长度不同，我们需要对较短的链表进行特殊处理。另外，如果相加的结果大于等于10，我们需要进行进位处理。
Go语言实现 - 迭代法
下面是使用Go语言实现的迭代法代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummyHead := &ListNode{
Val: 0}
p, q, curr := l1, l2, dummyHead
carry := 0
for p != nil || q != nil {
x := 0
y := 0
if p != nil {
x = p.Val
p = p.Next
}
if q != nil {
y = q.Val
q = q.Next
}
sum := carry + x + y
carry = sum / 10
curr.Next = &ListNode{
Val: sum % 10}
curr = curr.Next
}
if carry > 0 {
curr.Next = &ListNode{
Val: carry}
}
return dummyHead.Next
}
算法分析
- 时间复杂度: O(max(m, n))，其中 m 和 n 分别为两个链表的长度。
- 空间复杂度: O(max(m, n))，我们需要一个新链表来存储结果。
这个算法的时间复杂度和空间复杂度都是线性的，与较长的链表长度相同。
除了迭代法之外，还可以使用递归法来解决“两数相加”的问题。递归法的基本思想是将问题分解为更小的子问题，即相加两个链表的当前节点，然后递归地处理下一个节点。
解题思路 - 模拟法
通过链表的形式逐位计算两个数的和，同时考虑进位的情况。从两个链表的头节点开始，逐对节点相加，将结果创建为新的链表节点。如果两个链表的长度不一致，则将较短链表的剩余部分视为0进行处理。整个过程中，我们需要维护当前的进位信息。
Go语言实现 - 模拟法
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{0, nil} // 创建哑节点作为返回链表的头节点
curr := head
carry := 0 // 初始化进位为0
for l1 != nil || l2 != nil || carry > 0 {
sum := carry // 开始时将进位加入和中
if l1 != nil {
sum += l1.Val // 加上第一个链表的值
l1 = l1.Next // 移动到下一个节点
}
if l2 != nil {
sum += l2.Val // 加上第二个链表的值
l2 = l2.Next
}
carry = sum / 10 // 计算新的进位
curr.Next = &ListNode{sum % 10, nil} // 创建新的节点存储和的个位数
curr = curr.Next // 移动到新创建的节点
}
return head.Next // 返回哑节点的下一个节点，即结果链表的头节点
}
算法分析
- 时间复杂度: O(max(m,n))，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的最长长度。
- 空间复杂度: O(max(m,n))。新链表的长度最多为 max(m,n) + 1。
解题思路 - 优化模拟法
实际上，上述模拟法已经是相对高效的解法了。在具体实现过程中，进一步的优化空间不大。如果要优化，主要是代码层面的简化和优化，比如简化变量的使用，减少不必要的操作等，但算法本身的时间复杂度和空间复杂度已经达到了最优。
在这个问题中，关键是理解如何逐位相加并处理进位。优化的空间更多的在于代码的可读性和简洁性上，而不是算法复杂度的提升。
对于LeetCode题目2“两数相加”，实际上存在的解决方案主要围绕着迭代和递归两种思路展开。由于题目的特性和限制，解题方法相对固定，主要是如何处理两个链表的逐位相加以及进位处理。
主要方法
- 迭代法：这是最直观的方法，通过遍历两个链表，逐位计算和，并处理进位。迭代法的优点是直观易懂，实现简单，是大多数情况下的首选方法。
- 递归法：递归法利用递归函数来逐位相加，每一层递归处理一位。递归法的优点是代码更为简洁，但对于理解和调试来说可能稍微复杂一些。递归的深度等于链表的长度，因此对于非常长的链表可能会导致栈溢出。
其他方法的考虑
除了这两种方法，实际上没有根本上不同的算法来解决这个特定的问题。其他的所谓“方法”往往是对上述两种方法的变体或优化，例如：
- 优化存储：对于迭代法，可以通过直接在较长的链表上进行修改来节省空间，避免额外的空间分配。但这改变了输入数据，可能并不总是可接受的。
- 并行处理：理论上，如果链表足够长，可以考虑将链表分成几部分并行处理每一部分的加法。然而，这种方法在实践中很少使用，因为它增加了实现的复杂性，而且链表的遍历性质和计算机的内存访问模式使得并行化的效果并不明显。
