扭转链表
我试图使用递归来反转链表并为其编写以下代码。 该列表是开头的列表的开头。
node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); current->next = parent; printf("\n %d %d \n",current->value,parent->value); return parent; } } 我可以看到所有链接都被颠倒了。 然而，当我尝试显示时，我得到了数字的无限打印。 当我试图反转列表中最初的第一个数字的链接时，我怀疑是错误的。
我究竟做错了什么？
假设我有一个链表：
---------- ---------- ---------- ---------- | 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL ---------- ---------- ---------- ----------
您的代码将其转换为：
---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- | 1 | |--->| 2 | | | 3 | | | 4 | | ---------- ---------- ---------- ---------- ^ | | | ----------------------
请注意，第一个元素仍然指向2。
如果在前两个之后添加行parent->next = NULL ，您将得到：
---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- NULL<---| 1 | | | 2 | | | 3 | | | 4 | | ---------- ---------- ---------- ---------- ^ | | | ----------------------
这实际上是正确的结构。
完整的代码是:(您只需要为每个递归调用打印当前值）
node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); parent->next = NULL; current->next = parent; printf("\n %d \n",current->value); return parent; } }
到达列表末尾时，将返回最后一个节点。 然后，最后一个节点的下一个值被分配给它自己，因此你会产生一个不一致。 如果current为NULL，则返回NULL，如果返回为NULL，则忽略其余代码。
您忘记更新链接列表中第一个项目的next成员。 添加parent->next = NULL; 在递归调用之前。
您需要将新尾部（即旧头部）的下一个指针设置为NULL
编辑：这是一个递归版本
node *reverse_list_recursive(node *list) { node *parent = list; node *child = list->next; node *new_head; if (child == NULL) return parent ; /* new head */ new_head = reverse_list_recursive(child) child->next = parent; /* Old parent is the new child of the old child when reversed */ parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */ return new_head; }
我没有看到递归的好处，迭代也会起作用。 自从我编写C以来，它一直是永远的（并且没有简单的方法来测试以下语法错误……或者畏缩核心转储，但你明白了）。
node *reversed_list(node *list) { node *fwd=list;//Purely for readability node *last=null; node *next=null; node *rev=null; do { //Cache next next=fwd->next; //Set current rev=fwd; //Reset next to point back rev->next=last; //Update last last=fwd; //Forward ptr; fwd=next; } while (fwd!=null); return rev; }
很确定你的*list在你调用它之后是没用的，因为它现在指向列表的最后一个元素->next=null ，可以只更新它而不是返回指针。
更新（针对递归解决方案）
正如其他人所说，你的新尾部搞砸了（指向最后一个元素，但应该指向null）……并且你没有返回正确的头部，你返回第二个元素。 考虑使用您的算法列表a->b->null ：
p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a return a; //a->b, b->a, a returned //But what you wanted is a->null, b->a, and b returned
以下更新的代码将修复：
node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); current->next = parent; parent->next=null; //Fix tail printf("\n %d %d \n",current->value,parent->value); return current; //Fix head } }
使用列表a->b->null ：
p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a p->next=null //a->null return b; // b->a->null
行current = reverse_list_recursive(current); 你将新的列表头存储在当前，所以current->next = parent; 是错的。 新current是新的列表头，但您需要访问新的列表尾部，即OLD current ：
node* newhead = reverse_list_recursive(current); current->next = parent; printf("\n %d %d \n",current->value,parent->value); return newhead;
我能看到的一些问题：
- 您需要将新的最后一个节点的下一个指针设为NULL。
- 如果我最初将NULL传递给它，你现有的函数会被打破。
这里是递归代码来反转链表。
list * reverse(list * head) { if( head == NULL || head -> link == NULL ) return head; list *node = reverse( head- > link ); head -> link -> link = head; head -> link = NULL; return node; }
上面的Severl版本不能像OP那样工作，所以这里我的递归版测试很好：
node * reverseRecursive(node *p,node **head) { if(p->next == NULL) { *head = p; return p; } node *before; before = reverseRecursive(p->next,head); before->next = p; p->next = NULL; return p; } //call from main node*head; //adding value //assuming now head is now 1->2->3->4->NULL node* newHead; reverseRecursive(head,&newHead); //now now newHead is now 4->3->2->1->NULL