当head作为参数传递给以下代码时，它可以正常工作。由于我是C的新手，无法理解其工作原理。请帮我解释一下。
struct node *recursiveReverseLL(struct node *list)
{
struct node *revHead;
if (list == NULL || list->link == NULL)
{
return list;
}
revHead = recursiveReverseLL(list->link);
list->link->link = list;
list->link = NULL;
return revHead;
}
我不知道这些递归调用如何提供链接。即，如果链接是以下形式：
1 -> 2 -> 3 -> 4
那么它是如何改变的呢？
4 -> 3 -> 2 -> 1
这个问题的一般递归算法如下：
rest链接到first。head指针。以下是附有内联注释的代码：
struct node* recursiveReverseLL(struct node* first){
if(first == NULL) return NULL; // list does not exist.
if(first->link == NULL) return first; // list with only one node.
struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.
first->link->link = first; // make first; link to the last node in the reversed rest.
first->link = NULL; // since first is the new last, make its link NULL.
return rest; // rest now points to the head of the reversed list.
}
我希望这张图片能让事情更清晰:
(来源: geeksforgeeks.org)
.
替代方案：
struct node *head;
void reverse(struct node *prev, struct node *cur)
{
if(cur){
reverse(cur,cur->link);
cur->link = prev;
}
else{
head = prev;
}
}
/* Reverses a linked list, returns head of reversed list
*/
NodePtr reverseList(NodePtr curr) {
if (curr == NULL || curr->next == NULL) return curr; // empty or single element case
NodePtr nextElement = curr->next;
curr->next = NULL;
NodePtr head = reverseList(nextElement);
nextElement->next = curr;
return head;
}
struct node *reverse_recur(struct node *temp)
{
if(temp->link==NULL)
{
return temp;
}
struct node *temp1=temp->link;
temp->link=NULL;
return (reverse_recur(temp1)->link=temp);
}
struct linked_node * reverse_recursive(struct linked_node * head)
{
struct linked_node * first;/*stores the address of first node of the linked
list passed to function*/
struct linked_node * second;/* stores the address of second node of the
linked list passed to function*/
struct linked_node * rev_head;/*stores the address of last node of initial
linked list. It also becomes the head of the reversed linked list.*/
//initalizing first and second
first=head;
second=head->next;
//if the linked list is empty then returns null
if(first=NULL)
return(NULL);
/* if the linked list passed to function contains just 1 element, then pass
address of that element*/
if(second==NULL)
return(first);
/*In the linked list passed to function, make the next of first element
NULL. It will eventually (after all the recursive calls ) make the
next of first element of the initial linked list NULL.*/
first->next=NULL;
/* storing the address of the reverse head which will be passed to it by the
condition if(second==NULL) hence it will store the address of last element
when this statement is executed for the last time. Also here we assume that
the reverse function will yield the reverse of the rest of the linked
list.*/
rev_head=reverse(second);
/*making the rest of the linked list point to the first element. i.e.
reversing the list.*/
second->next=first;
/*returning the reverse head (address of last element of initial linked
list) . This condition executes only if the initial list is 1- not empty
2- contains more than one element. So it just relays the value of last
element to higher recursive calls. */
return(rev_head);
}
现在运行链表函数 1->2->3->4
函数列表为
1(first)->2(second) -> 3 -> 4
在reverse(&2)中
代码一直运行到rev_head=reverse(&3);
函数列表
2(first)->3 (second)-> 4
在reverse(&3)中
代码一直运行到rev_head=reverse (&4);
函数列表
3(first)-> 4 (second)
在reverse(&4)中 终止条件 second==NULL成立，所以执行返回语句， 返回地址为4的位置。
函数列表
4(first)-> NULL(second)
执行second->next=first; 后，链表变为
NULL<- 3(first) <-4 (second)
执行return (rev_head ); 将&4传递给rev(&2)，因为rev_head=&4
函数列表为
NULL<-2(first) 3(second)<-4
rev_head的值为被reverse(&3)返回的&4
执行second->next=first 后，链表变为
NULL<-2(first)<-3(second)<-4
执行return(rev_head); // rev_head=&4，这是由reverse(&2)返回的 将rev_head的值传递给rev(&1);
函数列表为
NULL<-1(first) 2(second)<-3<-4
rev_head的值为被reverse(&3)传递的&4
现在执行second->next =first，链表变为
NULL<-1(first) <- 2(second)<-3<-4
执行return(rev_head); // rev_head=&4，这是由reverse(&2)返回的 将rev_head的值传递给主函数。
希望这有所帮助。我花了很多时间才理解这个问题并写出这个答案。
reverse未声明。 - markroxor在我看来，似乎没有人提出过一种尾递归的算法。原则上，尾递归算法可以在不使用堆栈的情况下编译（前提是编译器足够智能），从而生成消耗更少内存的代码。
假设 TList 是一个自定义的单链表数据类型，它是指向具有 link 字段以访问列表中下一个元素的结构体的指针。
该算法如下：
```
TList reverse_aux(TList l, TList solution) {
if (l == NULL) {
return solution;
} else {
TList tmp = l->link;
l->link = solution;
return reverse_aux(tmp, l);
}
}
TList reverse(TList l) {
return reverse_aux(l, NULL);
}
```
这是一种优美的方法，可以递归地反转SLL：
1. struct node* head; // global head
2. void rec_reverse(struct node* prev, struct node* cur)
3. {
4. if (cur)
5. {
6. rec_reverse(cur, cur->next);
7. cur->next = prev;
8. }
9. else
10. head = prev;
11. }
以这种方式调用函数：
rec_reverse(NULL, head);
方法：
void rec_reverse(struct node* prev, struct node* cur) { if (cur==NULL) { head = prev; } else { next = cur->next; cur->next = prev; rec_reverse(cur, next); } }。 - Will Nessll *rev_list(ll *prev, ll *cur)
{
if (!cur) {
return prev;
}
ll *tmp = cur;
cur = cur->next;
tmp->next = prev;
prev = tmp;
return rev_list(prev, cur);
}
查找完整代码：https://github.com/vijaythreadtemp/Data-Structures-And-Algorithms/blob/master/rev_link_list_rec.cxx
To fix head also:
void reverse_list_recursive_internal (struct list **head, struct list *node)
{
/* last node, fix the head */
if (node->next == NULL) {
*head = node;
return;
}
reverse_list_recursive_internal(head, node->next);
node->next->next = node;
node->next = NULL;
}
void reverse_list_recursive (struct list **head)
{
if (*head == NULL) {
return;
}
reverse_list_recursive_internal(head, *head);
}
1->2->null。为了使其通用，我们将始终从first节点引用其他节点。要反转它，设置first(1)->next(2)->next(null) = first(1)使其变成1<->2，然后first(1)->next(2) = null将导致null<-1<-2。递归使用此规则。 - SMUsamaShah