c - 反转单链表的递归方法？

Question

我在中看到过这个递归程序(C语言)

http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

用于反转单链表。

void recursiveReverse(struct node** head_ref){

struct node* first;
struct node* rest;

/* empty list */
if (*head_ref == NULL)
   return;   

/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref;  
rest  = first->next;

/* List has only one node */
if (rest == NULL)
   return;   

/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next  = first;  

/* tricky step -- see the diagram */
first->next  = NULL;          

/* fix the head pointer */
*head_ref = rest;}

在程序的这一步，

/* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first; 

我可以写“rest->next = first;”而不是“first->next->next = first;”吗？

或者写“first->next->next = first;”有什么意义吗？

Answer 1

那么，当您尝试这种改变时发生了什么？ 当然您可以编写它……但语义可能会改变。

将 first->next 分配给 rest 并不强制它们始终相同。您紧接在前的语句将 指针 传递给 rest 到 recursiveReverse。简而言之，您期待休息来改变。

rest 现在应该指向 reversed 列表剩余部分的头部。这不再是first->next；那现在应该是反转列表的结尾，其中rest 是该列表的头部。

这是否足够好地解释事情？如果没有，请输入一些打印语句来说明您的程序在每种情况下的作用。