在不使用指针指针的情况下反转链接列表
我已经使用以下代码成功实现了2指针解决方案：
void list_reverse(t_list **begin_list) { t_list *new_root; t_list *root; t_list *next; new_root = 0; root = *(begin_list); while (root) { next = root->next; root->next = new_root; new_root = root; root = next; } *begin_list = new_root; } 哪个工作正常 – 至少根据我的测试。 现在我想尝试仅使用单个指针来反转链表，而不return ，所以我尝试将我的代码转换为void list_reverse(t_list *begin_list) ，但当然*begin_list = new_root不起作用，因为我无法更改begin_list 。 其余的似乎工作。
如何在没有双指针的情况下修改begin_list ？
编辑：结构是：
typedef struct s_list { struct s_list *next; void *data; } t_list;
您可以通过交换第一个和最后一个节点（浅拷贝）来反转列表，然后反转列表。 这样，最后一个节点的内容将在头指针已经指向的初始节点中结束。
这是一个实现：
void swap(struct node *a, struct node *b) { struct node tmp = *a; *a = *b; *b = tmp; } void reverse(struct node *h) { // Null list and single-element list do not need reversal if (!h || !h->next) { return; } // Find the last node of the list struct node *tail = h->next; while (tail->next) { tail = tail->next; } // Swap the tail and the head **data** with shallow copy swap(h, tail); // This is similar to your code except for the stopping condition struct node *p = NULL; struct node *c = tail; do { struct node *n = c->next; c->next = p; p = c; c = n; } while (c->next != tail); // h has the content of tail, and c is the second node // from the end. Complete reversal by setting h->next. h->next = c; }
演示。
函数有三种主要方式可以为其调用者提供计算值。
-
它可以
return该值，或者包含它的对象，或指向这样一个对象的指针（在最后一种情况下，提供指向的对象超过函数调用）。 -
它可以通过调用者提供的指针修改调用者可见的对象。
-
它可以将计算值记录在调用者可见的文件范围变量中。
还有其他替代方案，主要涉及I / O，但这些方法通常符合（3）的精神。
您不得使用（1）。 你不能以你提出的方式使用（2）。 可能是（3）是预期的答案，但那是丑陋的，真的不应该被推荐。 那么该怎么办？
也许你只是咬紧牙关并使用文件范围变量，但是如果你被允许寻求呼叫者的帮助和/或在列表的forms上提出要求那么你还有另一种可能性：让呼叫者通过列表反转时不会改变的指针 – 即指向包含指向列表头的指针的结构的指针。 然后该函数不需要修改该指针; 它通过指向对象返回新的列表头。
通常，人们使用表示整个列表的单独结构类型来做这种事情。 但是，如果您想一下，您会发现现有的列表节点类型已经具有合适的forms。 如果您无法引入新结构，那么您可以使用现有结构 – 只需将列表中的第一个节点视为其余元素上的非数据承载句柄。 这有时被称为虚拟头节点，并且使用一个在许多方面提供更简单的函数实现的列表。
看看这个：
void reverse(struct node* head) { struct node *curr=head; struct node *next=NULL; struct node *prev=NULL; while(curr) { next=curr->next; //we're basically stashing the next element curr->next=prev; //setting next pointer to the previous element prev=curr; //previous is now current curr=next; //and updating the current from the stashed value } }