需要帮助我的大脑在Leetcode 2.添加两个数字(链表问题)

Question

我用这个问题作为一个例子，但我真正困难的是我对链表的理解，以及我们如何以迭代的方式构建它们。问题在这里:

给定两个非空链表，表示两个非负整数。这些数字以相反的顺序存储，它们的每个节点包含一个数字。将两个数相加，并以链表的形式返回和。

你可以假设这两个数字不包含任何前导零，除了数字0本身。

Input: l1 = [2,4,3], l2 = [5,6,4] 
Output: [7,0,8]
Explanation: 342 + 465 = 807.

我在试着理解这个人的解决方案。我的困惑在于他是如何构建链表added的。他在开始时将其定义为一个带有一个数字的列表节点，并且直到最后返回它时才对它做任何操作。这是怎么建成的?

我理解current_node一开始设置为added。但是当循环迭代时，current_node.next不断更新——这不会只是改变current_node.next吗?然后我们最终会得到一个长度为2的链表?其中第一个值是第一个节点(l1.val + l2.val) % 10，然后第二个值将是最后一个(carry_over + l1.val + l2.val) % 10?当然，我知道情况并非如此，因为他最终得到的是正确的链表，但我真的无法理解。

我想我真的不明白如何迭代地建立一个链表。一个简单的解释将非常感激，谢谢!

Answer 1

current_node被初始化为引用与added相同的节点，使用以下语句:

current_node = added

它们现在都引用最终列表的第一个(当时也是唯一的)节点。

我们可以这样想象:

added  current_node
│        │
┌──┴────────┴───┐
│ val: 4        │
│ next: None    │
└───────────────┘

演示者在视频中9点解释:

当我们循环时，我们将改变每个节点

这"altering"也适用于第一个节点，如上图所示。

在循环中，current_node.next被分配一个对新节点的引用。这里有一个重要的发现，在第一个中迭代，这意味着added.next被分配了引用:两者引用同一个节点(在第一次迭代中)，所以下面的语句(参见视频中的11:45):

current_node.next = ListNode(val = (carry_over + l1.val + l2.val) % 10)

…将导致如下:

added  current_node
│        │
┌──┴────────┴───┐     ┌───────────────┐
│ val: 4        │     │ val: 9        │
│ next: ──────────────┤ next: None    │
└───────────────┘     └───────────────┘

然后current_node = current_node.next将把引用移动到新节点:

added                  current_node
│                         │
┌──┴────────────┐     ┌──────┴────────┐
│ val: 4        │     │ val: 9        │
│ next: ──────────────┤ next: None    │
└───────────────┘     └───────────────┘

毫无疑问，added总是引用头。但更重要的不变量是:在每次迭代开始时，current_node引用当前尾部该列表的节点。因此，current_node.next的任何更新实际上都会影响以added为头节点的列表。