在链表中使用节点指针如何改变递归？

Question

我用临时节点'nextnode'指向head或cur的下一个节点：

SinglyLinkedListNode* removeDuplicates(SinglyLinkedListNode* head) {
    if ( head == NULL ) return NULL;
    SinglyLinkedListNode *nextnode = head->next;
    while ( nextnode != NULL && head->data == nextnode->data ) {
        nextnode = nextnode->next;
    }
    head->next = removeDuplicates( nextnode );
    return head;
}

此代码工作正常...但如果我更改

head->next = removeDuplicates( nextnode );

至

head->next = removeDuplicates( head->next);

代码输出与输入相同的列表。

但是如果我在所有地方删除 nextnode 并使用 head->next 代替 nextnode，代码工作正常！

到底发生了什么，让它发挥作用？我错过了什么？

使用 head->next 和 nextnode 时这段代码会发生什么？我只是想了解它在内存分配中的工作原理，以便更好地理解递归。

Answer 1

以这个列表为例：

head
  ↓
  1 → 2 → 2 → 3 → 3 → 3 → 4

在函数的第一次调用中，nextnode 将指向 [2]，并且 while 条件将立即为假，因为数据不同 (1 != 2)。所以我们有：

head  nextnode
  ↓   ↓  
  1 → 2 → 2 → 3 → 3 → 3 → 4

然后进行第一个递归调用，在该执行上下文中，还有另一个 head 变量，它被设置为调用者 nextnode 的值。为了更好地跟踪这个 head 变量，我将其称为 head2，并且当我们在原始调用中谈到该变量时将继续引用 head：

head head2
  ↓   ↓  
  1 → 2 → 2 → 3 → 3 → 3 → 4

创建了一个新的nextnode变量，这次while循环将进行一次迭代，因为有一个重复值(2)。当 nextnode 指向具有 3:

的节点时，迭代停止

head head2  nextnode
  ↓   ↓       ↓   
  1 → 2 → 2 → 3 → 3 → 3 → 4

进行了另一个递归调用。我们再次得到一个新的 head 变量，我将其命名为 head3:

head head2  head3
  ↓   ↓       ↓   
  1 → 2 → 2 → 3 → 3 → 3 → 4

同样，将创建一个新的 nextnode。这次它最终指向节点 4:

head head2  head3       nextnode
  ↓   ↓       ↓           ↓
  1 → 2 → 2 → 3 → 3 → 3 → 4

进行更深层次的递归调用：

head head2  head3       head4
  ↓   ↓       ↓           ↓
  1 → 2 → 2 → 3 → 3 → 3 → 4

这次新的 nextnode 变量将变为 NULL，因此我们使用参数 NULL 进行递归调用。我们正处于递归的末尾，因为这个最深的调用将立即 return NULL。我们回到调用的地方，看到 head4->next 被分配了这个 NULL。在这种情况下，这个赋值没有区别，因为 head4->next 已经是 NULL.

我们回溯到递归树中的上一层：head4 是 returned。我们确实看到了修改的发生。这个 returned head4 被分配给 head3->next，因此第二个和第三个值为 3 的节点都被踢出列表，只有一个分配：

head head2  head3       head4
  ↓   ↓       ↓           ↓
  1 → 2 → 2 → 3 →         4

我们又回溯了一步，这次 head3 被 return 赋值给 head2->next。现在第二个值为2的节点被踢出：

head head2  head3   head4
  ↓   ↓       ↓       ↓
  1 → 2 →     3 →     4

又一次回溯：head2 被 return 分配给 head->next。这没有区别，因为 head->next 已经指向 head2。 top-level 函数调用 return 和 head，我们就完成了。

与`head->next = removeDuplicates( head->next);`

这个改动确实会破坏算法。它使 nextnode 的值变得无关紧要。 while 循环现在无用，因为代码没有使用 nextnode 的新值。您不妨删除该循环和变量 nextnode，然后很明显没有节点被删除。

一个关键的观察是 removeDuplicates 总是 returns 你作为参数传递给它的节点 ，所以改变的语句实际上是在做：

head->next = head->next

...什么都不做，它是代码中唯一列表链被更改的地方。没有其他地方是 next 属性改变。

if I remove nextnode in all places and use head->next in place of nextnode, the code works fine!

确实如此。在这种情况下，该函数不需要 return 任何东西，因为 duplicate-removal 永远不需要更改列表的 head。所以代码看起来像这样：

void removeDuplicates(SinglyLinkedListNode* head) {
  if ( head == NULL ) return;
  while ( head->next != NULL && head->data == head->next->data ) {
    head->next = head->next->next;
  }
  removeDuplicates( head->next );
}

我们可以再次对示例列表进行与此答案顶部相同的分析（请在一张纸上这样做），您会得出结论，它也可以有效地删除重复项。不同之处在于，这里实际删除在 while 循环中一次发生一个节点（每次迭代只删除一个节点），而在原始代码中它发生在回溯期间，它实际上可以删除多个重复节点一步到位（正如我们在一次作业中 3 → 3 → 3 → 4 变成 3 → 4 的情况中看到的那样），所以通常原始代码有时可以用更少的作业完成工作，当然当有很多重复时列表中的值。

原始代码中也有较少的->next引用。

由于这些差异，原始代码理论上运行会快一点。

在链表中使用节点指针如何改变递归？

How does using node pointer in linked list changes the recursion?

c++

recursion

linked-list

data-structures

singly-linked-list

与`head->next = removeDuplicates( head->next);`

在链表中使用节点指针如何改变递归？

How does using node pointer in linked list changes the recursion?

c++

recursion

linked-list

data-structures

singly-linked-list

与head->next = removeDuplicates( head->next);

与`head->next = removeDuplicates( head->next);`