LeetCode题集-2 - 两数相加

这个题目是什么意思呢？简单来说就是把两个链表平铺开，头节点对齐，然后从头开始相同的节点相加，满10则进位，进位值与下个节点继续相加，当一个链表没有节点时候则可以把没有节点当做0继续与有节点的链表继续相加。具体示例如下：

到这里不知道你是否已经有解题思路了呢？

解法一：递归法

我第一反应就是递归，为什么？想想题目，对两个链表相同节点位置值按顺序求值，第一个算完算第二个，以此类推直至所有节点计算完成，这不正好使用递归吗，定义一个方法计算两个节点和，然后以头节点的下个节点作为递归点，即计算头节点后，头节点的下个节点计算直接调用自身方法直至所有节点计算完成，具体代码如下：

public static ListNode AddTwoNumbersRecursion(ListNode l1, ListNode l2)

{

return AddTwoNumbersRecursive(l1, l2, 0);

}

private static ListNode AddTwoNumbersRecursive(ListNode l1, ListNode l2, int carry)

{

//当两个链表节点都为空并且进位值等于0，则结束递归

if (l1 == null && l2 == null && carry == 0)

{

return null;

}

//以进位值为初始值定义两节点和变量，

var sum = carry;

//如果l1节点不为空，则累加其节点值，并且把其下个节点赋值给自身，用于下次迭代

if (l1 != null)

{

sum += l1.val;

l1 = l1.next;

}

//如果l2节点不为空，则累加其节点值，并且把其下个节点赋值给自身，用于下次迭代

if (l2 != null)

{

sum += l2.val;

l2 = l2.next;

}

//计算进位值

carry = sum / 10;

//以当前位值，创建下一个节点

return new ListNode(sum % 10)

{

//递归点

next = AddTwoNumbersRecursive(l1, l2, carry)

};

}

然后我们运行代码验证一下，结果如下：

解法二：迭代法

我们知道因为每次递归都会需要额外的栈空间，因此深度递归可能会引发一系列性能问题，因此我们是否还有其他办法呢？

递归有个同义词叫迭代，而迭代只需要在一个循环里重复执行一个计算即可，这样就可以避免递归产生的问题。

因此我们只需要把递归方法改造成迭代方法即可，里面的解题思路基本都是一样的，只不过是不通的写法。代码如下：

public static ListNode AddTwoNumbersIteration(ListNode l1, ListNode l2)

{

//创建头节点，即第一位计算结果

var head = new ListNode(0);

//用于迭代节点

var current = head;

//初始化进位值

int carry = 0;

//当两个链表节点都不为空并且进位值不等于0，则继续迭代

while (l1 != null || l2 != null || carry != 0)

{

//以进位值为初始值定义两节点和变量，

var sum = carry;

//如果l1节点不为空，则累加其节点值，并且把其下个节点赋值给自身，用于下次迭代

if (l1 != null)

{

sum += l1.val;

l1 = l1.next;

}

//如果l2节点不为空，则累加其节点值，并且把其下个节点赋值给自身，用于下次迭代

if (l2 != null)

{

sum += l2.val;

l2 = l2.next;

}

//计算进位值

carry = sum / 10;

//以当前位值，创建下一个节点

current.next = new ListNode(sum % 10);

//把下个节点赋值给当前迭代节点，继续下次迭代

current = current.next;

}

//返回实际结果链表的头节点

return head.next;

}

运行结果如下：

对于这一题核心解题思路是一样，问题在于如何选择方法，递归有递归的好处，迭代有迭代的好处，因此要根据自己实际情况进行选择。

下面对递归和迭代做个点单对比：

递归：代码更简洁直观，逻辑更接近问题的自然描述易于理解；但是递归会消耗更多内存，深度递归可能会导致栈溢出。

迭代：节省内存，性能会更好；但是代码更难理解。

题目到这里就做完了，但是不知道有没有人会有这样的疑惑？

在迭代法中，链表head是一个引用类型，并且被赋值给了链表current，而链表current在迭代中不停的被current.next覆盖，那么为什么这个覆盖过程没有影响到链表head？导致head为整个链表的最后一个节点？最后返回的head.next还是正确的答案？

你知道为什么吗？

注：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner