反转链表数据结构代码需要视觉解释指南吗? [英] Visual Explanation Guidance needed for reversal of Linked List datastructure code?

问题描述

我有以下用于反转链表的代码.我在 while 循环中感到困惑，所以如果有人能提供它实际工作方式的视觉解释，我肯定会很感激.

I have following piece of code for reversing the linked list. I am getting confused in while loop and so would certainly appreciate if someone can provide visual explanation of how actually it's working.

 static void Reverse (struct node** headRef)
{
     struct node* result = NULL;
     struct node* current = *headref;
     struct node* next;

     while(current != NULL)
     {
        next = current->next;
        current->next = result;
        result = current;

        current = next;
     }     
     *headRef = result;

}

推荐答案

好的，这是我试图让 valya 的答案更清晰的尝试(虽然我认为它已经很不错了):

OK, here's my attempt to make valya's answer even clearer (though I thought it was pretty good already):

假设我们有这个列表:

// a->b->c->d->e->NULL

我们从第一个节点开始，a，它包含一个指向 b 的指针 (next):

We start at the first node, a, which contains a pointer (next) to b:

// a->b ...

行 next = current->next; 将 next 设置为 b(足够简单).下一行 current->next = result; 这样做:

The line next = current->next; sets next to b (simple enough). The next line current->next = result; does this:

// NULL<-a  b ... (notice there is no longer a pointer from a to b)

然后我们有 result = current; 它将 result 设置为 a(同样，足够简单).最后，我们有所有重要的 current = next;，它将 current 设置为 b.

Then we have result = current; which sets result to a (again, simple enough). And finally, we have the all important current = next;, which set current to b.

所以在while循环的下一次迭代中，将next设置为b，result设置为a>，并且 current 设置为 b，我们重新开始:

So on the next iteration of the while loop, with next set to b, result set to a, and current set to b, we start over:

next = current->next;

// NULL<-a<-b  c ...
current->next = result;

result = current;

然后我们再做一次:

next = current->next;

// NULL<-a<-b<-c  d ...
current->next = result;

result = current;

一旦我们到达链表中的最后一项(在本例中为e)，就会发生这种情况:

Once we've gotten to the last item in the linked list (e in this example), this happens:

next = current->next; // next becomes NULL

// NULL<-a<-b<-c<-d<-e
current->next = result;

result = current; // result is now e

current = next; // current is now NULL

现在，由于current为NULL，while循环终止，剩下:

Now, since current is NULL, the while loop terminates, and we are left with:

*headRef = result;

，正如您现在看到的，使 headRef 指向 e，将 e 视为我们链表中新的第一项，e->next 指向 d，d->next 指向 c，等等

which, as you can see now, makes headRef point to e, treating e as the new first item in our linked list, with e->next pointing to d, d->next pointing to c, etc.

这篇关于反转链表数据结构代码需要视觉解释指南吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！