在c中递归地反转链表
当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
然后hw被改变为，
4 -> 3 -> 2 -> 1
一般的递归算法是：
- 将列表分为
2部分 – 第一个节点和列表的其余部分。 - 递归调用反向链接列表的
rest。 - 将
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. }
我希望这张照片能让事情更加清晰：
图片http://sofzh.miximages.com/c/Linked-List-Rverse.gif 。
替代解决方案：
struct node *head; void reverse(struct node *prev, struct node *cur) { if(cur){ reverse(cur,cur->link); cur->link = prev; } else{ head = prev; } }
在main中，调用reverse（NULL，head）;
/* 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); }
让链表为1-> 2 – > 3 – > 4
c中的函数是 –
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. ie 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的function
- 内部反向（＆1）代码运行直到rev_head = reverse（＆2）; //这里＆1是地址1。
function列表是
1（第一） – > 2（第二） – > 3 – > 4
-
内部反向（＆2）代码运行，直到rev_head = reverse（＆3）; function列表
2（第一） – > 3（第二） – > 4 -
内部反向（＆3）代码运行，直到rev_head = reverse（＆4）; 如果function列出
3（第一） – > 4（第二） -
内部反向（＆4）终止条件第二次== NULL为真，因此返回执行并返回地址4。
function列表
4（第一） – > NULL（第二个）
- 回到反向（＆3）function列表是
NULL <-3（第一个）4（第二个）
以及返回的rev_head =＆4的值
执行second-> next = first之后; 列表变成了
NULL < - 3（第一个）< - 4（秒）
return（rev_head）; 由于rev_head =＆4，执行传递＆4
- 回到转（＆2）
function列表是
NULL <-2（第一）3（第二）< - 4
和rev_head是＆4，由rev（＆3）返回
在执行second-> next = first之后，列表变为
NULL <-2（第一）< - 3（第二）< - 4
返回（rev_head）; 执行返回＆4到rev（＆1）;
- 回到转（＆1）
function列表是
NULL <-1（第一）2（第二）< - 3 <-4
并且rev_head的值是＆4，它通过反向传递（＆3）
现在second-> next = first执行，列表变为
NULL <-1（第一）< - 2（第二）< - 3 <-4
返回（rev_head）; 执行// rev_head =＆4，它由reverse（＆2）返回，并且rev_head的值传递给main函数。
希望这可以帮助。 我花了很多时间来理解这一点并写下这个答案。
这是一种可以跟随递归反转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);
做法：
- 递归调用函数（第6行），我们转到链表的最后一个节点。
- 然后我们用最后一个节点的地址更新head（第10行）。
- 最后，我们将每个节点的链接指向其先前的节点（第7行）。
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); }
在我看来，没有人提出过尾递归的算法。 原则上，尾递归算法可以在没有堆栈的情况下编译（假设编译器足够智能），从而产生消耗更少内存的代码。
假设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); }
“`