链接列表反转

Question

我正在尝试弄清楚这种方法如何用于反转链表。但我只是不知道这里发生了什么。我需要知道它如何将指针切换到另一个方向。感谢您的帮助。

void reverse(struct node** head_ref)
{
      Node* prev = NULL;
      Node* current = *head_ref;
      Node* next;
      while (current != NULL)
      {
          next = current->next;
          current->next = prev;
          prev = current;
          current = next;
      }
      *head_ref = prev;
}

Answer 1

没有必要反转这个列表，因为它是双重链接的，但这是这个函数的工作原理......

我们从元素列表开始：

list:    [A -> B -> C -> NULL]
current: A
next:    UNINITIALISED
prev:    NULL

首先，我们看元素A。它的"下一个"指针指向 B。我们将该指针指向 B 并将其备份到局部变量"next"中。然后我们取 A 的 'next' 并将其指向当前的本地 'previous'，当前为 NULL。接下来，我们更新本地"上一个"指针并将其设置为 A，最后将本地"当前"指针设置为 A 的"下一个"，即元素 B。

list:    [A -> NULL], [B -> C -> NULL]
current: B
next:    B
prev:    A

现在，我们已经完成了循环的第一次迭代，所以我们回到顶部并再次跟进它。我们将本地"next"设置为B的"next"，即C。我们将 B 的"next"设置为当前的本地"previous"，即 A。最后，我们将本地"上一个"更新为B，将本地"当前"更新为C。

list:    [B -> A -> NULL], [C -> NULL]
current: C
next:    C
prev:    B

现在模式非常明显，所以我将跳过演练...

list:    [C -> B -> A -> NULL]
current: NULL
next:    NULL
prev:    C

现在，电流为 NULL，因此 while 循环中的布尔表达式返回 false，我们退出循环。最后发生的事情是，列表的新"头"指针现在设置为指向新的头 C。