0

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

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;
}
4

1 回答 1

1

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

我们从元素列表开始：

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

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

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

现在，我们已经完成了循环的第一次迭代，所以我们回到顶部并再次执行它。我们将本地'next'设置为B的'next'，即C。我们将B的'next'设置为当前本地'previous'，即A。最后，我们将本地'previous'更新为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

现在，current 为 NULL，所以 while 循环中的布尔表达式返回 false，我们退出循环。最后发生的事情是列表的新“头”指针现在设置为指向新头 C。

于 2013-11-06T01:51:34.567 回答