我正在为添加两个链表而 geeksforgeeks.com 求和。我对提供的答案感到困惑。
Node addTwoLists(Node first, Node second) {
Node res = null; // res is head node of the resultant list
Node prev = null;
Node temp = null;
int carry = 0, sum;
while (first != null || second != null) //while both lists exist
{
// Calculate value of next digit in resultant list.
// The next digit is sum of following things
// (i) Carry
// (ii) Next digit of first list (if there is a next digit)
// (ii) Next digit of second list (if there is a next digit)
sum = carry + (first != null ? first.data : 0)
+ (second != null ? second.data : 0);
// update carry for next calulation
carry = (sum >= 10) ? 1 : 0;
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = new Node(sum);
// if this is the first node then set it as head of
// the resultant list
if (res == null) {
res = temp;
} else // If this is not the first node then connect it to the rest.
{
prev.next = temp;
}
// Set prev for next insertion
prev = temp;
// Move first and second pointers to next nodes
if (first != null) {
first = first.next;
}
if (second != null) {
second = second.next;
}
}
if (carry > 0) {
temp.next = new Node(carry);
}
// return head of the resultant list
return res;
}
我知道我们已经创建了三个节点res，prev和temp，我不明白它们中的每一个是如何同时更新的。
if (res == null) {
res = temp;
} else // If this is not the first node then connect it to the rest.
{
prev.next = temp;
}
就像这里一样，当我们在 prev.next 中添加第二个元素时，如何在 res 中添加它。 及以下：
if (carry > 0) {
temp.next = new Node(carry);
}
如果我们在 temp 中添加最后一个元素，它将如何在 res？ 代码似乎正在工作，但我很难理解这个概念。
请帮忙。提前谢谢。
res、prev 和 temp 是对节点的引用。当您编写类似res = tmp;的内容时，这意味着现在 res 和 tmp 引用同一个 Node 实例，并且当您使用 tmp 引用时，使用 res引用对此实例所做的任何更改都将保留。
这里是相同的代码，但有额外的注释来帮助解释正在发生的事情。此代码似乎是从链接列表中获取两个头节点，其中每个节点包含一个数字，然后将这些数字相加以创建一个新的个位数列表(例如 1->2->3 和 5->6->7->8 = 1+5->2+6->3+7->0+8。请注意，第三个集合会导致结转，因此返回列表中的最终值将为 6->8->0->9(。 因此，此代码不是一起添加到两个链接列表中，而是添加包含的数据 在两个列表的每个节点中，并将结果放入第三个列表中。
我在代码中的附加注释以 WCK 为前缀 -
Node addTwoLists(Node first, Node second) {
Node res = null; // res is head node of the resultant list
Node prev = null;
Node temp = null;
int carry = 0, sum;
while (first != null || second != null) //while both lists exist WCK actually this is While at least one of the lists exists, I believe the comment is wrong and the code is right
{
// Calculate value of next digit in resultant list.
// The next digit is sum of following things
// (i) Carry
// (ii) Next digit of first list (if there is a next digit)
// (ii) Next digit of second list (if there is a next digit)
sum = carry + (first != null ? first.data : 0)
+ (second != null ? second.data : 0);
// update carry for next calulation
carry = (sum >= 10) ? 1 : 0; // WCK - assumes sum <20; is only carrying at most 1
// update sum if it is greater than 10
sum = sum % 10;
// Create a new node with sum as data
temp = new Node(sum);
// if this is the first node then set it as head of
// the resultant list
// WCK - the first time through the loop, res will be null
// WCK - each subsequent time through the loop, the else is invoked to link the new node to the one from the previous iteration thus linking them
if (res == null) {
res = temp; //WCK - as @ardenit says, both res and temp point to the same node at this point
} else // If this is not the first node then connect it to the rest.
{
prev.next = temp;
}
// Set prev for next insertion
// WCK - now they are starting to set up for the next iteration.
// WCK - the first time through, res, prev and temp all point to the same node after this statement is executed.
prev = temp;
// Move first and second pointers to next nodes
if (first != null) {
first = first.next;
}
if (second != null) {
second = second.next;
}
// WCK - the first time through the loop, both of the lists passed in
// have been advanced to the next node in their respective lists.
// res and prev will point to the temp. As the next iteration of the loop
// starts, temp will be pointed to a new node while res and prev will
// still point to the same node created in the first iteration. As the
// second iteration executes, prev is set to point to the new temp
// where you see (prev.next = temp) and then prev is advanced to the
// this new node as well. res will not be changed again (it is only set
// once in the first iteration)
}
// WCK - now that the loop is finished, there may be a final carry value
if (carry > 0) {
temp.next = new Node(carry);
}
// return head of the resultant list
return res;
}