C语言 在c中递归地反转链表

Reversing a linkedlist recursively in c

提问by rampireram

The following code works fine when head is sent as a parameter to it. As I am new to C, I couldn't understand how it works. Help me out please.

当 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;
}

I dont know how the links are provided using those recursive calls. ie) if the links are as,

我不知道如何使用这些递归调用提供链接。即）如果链接是，

1 -> 2 -> 3 -> 4 

then hw is it changed as,

那么 hw 被更改为，

4 -> 3 -> 2 -> 1

回答by codaddict

The general recursive algorithm for this is:

通用的递归算法是：

1. Dividethe list in 2parts - first node and rest of the list.
2. Recursively call reverse for the restof the linked list.
3. Link restto first.
4. Fix headpointer

1. Divide2部分列表- 第一个节点和列表的其余部分。
2. rest对链表的递归调用 reverse 。
3. 链接rest到first.
4. 修复head指针

Here is the code with inline comments:

这是带有内联注释的代码：

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.
}

I hope this picture will make things clearer:

我希望这张图能让事情更清楚：

_{(source: geeksforgeeks.org)}
.

_{（来源：geeksforgeeks.org）}
。

回答by Aakash Arayambeth

Alternate solution :

替代解决方案：

struct node *head;
void reverse(struct node *prev, struct node *cur)
{
   if(cur){
      reverse(cur,cur->link);
      cur->link = prev;
    }
    else{
      head = prev;
    }
}

In main, call reverse(NULL,head);

在 main 中，调用 reverse(NULL,head);

回答by n3wb

/* 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;
}

回答by Sanjith Bravo Dastan

Another solution:

另一种解决方案：

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);

}

回答by Sanjith Bravo Dastan

Let the linked list be 1-> 2 -> 3 ->4

让链表为 1-> 2 -> 3 -> 4

the function in c is--

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. 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);
}

now running the function for the linked list 1-> 2-> 3 -> 4

现在运行链表 1-> 2-> 3 -> 4 的函数

• inside reverse(&1) the code runs until rev_head=reverse(&2); // here &1 is address of 1.

• 在 reverse(&1) 中，代码运行直到 rev_head=reverse(&2); // 这里 &1 是 1 的地址。

list of function is
1(first)->2(second) -> 3 -> 4

函数列表是
1(first)->2(second)->3->4

• inside reverse(&2) code runs until rev_head=reverse(&3); list of function
  2(first)->3 (second)-> 4

• inside reverse(&3) code runs until rev_head=reverse (&4); list if function
  3(first)-> 4 (second)

• inside reverse(&4) terminating condition second==NULL is true so return is executed and address of 4 is returned.

• 内部 reverse(&2) 代码运行直到 rev_head=reverse(&3); 函数列表
  2(first)->3(second)->4

• 内部 reverse(&3) 代码运行直到 rev_head=reverse (&4); 列出函数
  3（第一）-> 4（第二）

• 内部 reverse(&4) 终止条件 second==NULL 为真，因此执行 return 并返回 4 的地址。

list of function

功能列表

4(first)-> NULL(second)

4（第一）-> NULL（第二）

• back to reverse(&3) list of function is
  NULL<-3(first) 4 (second)
  and the value of rev_head=&4 which was returned

• 返回 reverse(&3) 函数列表为
  NULL<-3(first) 4 (second)
  和返回的 rev_head=&4 的值

after executing second->next=first; list becomes

执行 second->next=first 后；列表变成

NULL<- 3(first) <-4 (second)

NULL<- 3（第一）<-4（第二）

return (rev_head ); is executed which passes &4 because rev_head=&4

返回 (rev_head); 执行通过 &4 因为 rev_head=&4

• back to rev(&2)

• 回到 rev(&2)

list in function is

功能列表是

NULL<-2(first) 3(second)<-4

NULL<-2(第一) 3(第二)<-4

and rev_head is &4 which was returned by rev(&3)

并且 rev_head 是 &4 由 rev(&3) 返回

after executing second->next=first , list becomes

执行 second->next=first 后，列表变为

NULL<-2(first)<-3(second)<-4

NULL<-2(第一)<-3(第二)<-4

return(rev_head); is executed which returns &4 to rev(&1);

返回（rev_head）；执行返回 &4 到 rev(&1);

• back to rev(&1)

• 回到 rev(&1)

list in function is

功能列表是

NULL<-1(first) 2(second)<-3<-4

NULL<-1(第一) 2(第二)<-3<-4

and value of rev_head is &4 which was passed by reverse(&3)

rev_head 的值是 &4，由 reverse(&3) 传递

now second->next =first is executed and list becomes

现在 second->next =first 被执行并且列表变成

NULL<-1(first) <- 2(second)<-3<-4

NULL<-1（第一）<- 2（第二）<-3<-4

return(rev_head); is executed // rev_head=&4 which was returned by reverse(&2) and the value of rev_head is passesd to the main function.

返回（rev_head）；执行 // rev_head=&4 由 reverse(&2) 返回，rev_head 的值被传递给主函数。

hope this helps. It took me quite a lot of time to understand this and also to write this answer.

希望这可以帮助。我花了很多时间来理解这一点并写下这个答案。

回答by Krishna Durgam

    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);
}

回答by Amit Upadhyay

This is a beautiful approach one can follow to reverse SLL recursively:

这是一种可以用来递归反转 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.    }

Call the function this way:

以这种方式调用函数：

rec_reverse(NULL, head);

Approach:

方法：

• Calling the function recursively (line 6) we go to the last node of linked list.
• Then we update head with the address of the last node (line 10).
• Finally, we point link of each node to its previous node (line 7).

• 递归调用该函数（第 6 行），我们转到链表的最后一个节点。
• 然后我们用最后一个节点的地址更新 head（第 10 行）。
• 最后，我们将每个节点的链接指向其前一个节点（第 7 行）。

回答by FSp

It seems to me that nobody has suggested an algorithm that is tail-recursive. In principle, a tail-recursive algorithm can be compiled without a stack (provided that the compiler is smart enough), thus producing code that consumes less memory.

在我看来，没有人提出过尾递归算法。原则上，尾递归算法可以在没有堆栈的情况下进行编译（前提是编译器足够聪明），从而生成占用更少内存的代码。

Assume TListis a custom data-type for single-linked list, it is a pointer to a structure that as a linkfield for accessing the next element in the list.

假设TList是单链表的自定义数据类型，它是一个指向结构的指针，作为link访问列表中下一个元素的字段。

The algorithm is the following:

算法如下：

```

``

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);
}

```

``

回答by Vijaymahantesh Sattigeri

ll *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);
}

Find complete code : https://github.com/vijaythreadtemp/Data-Structures-And-Algorithms/blob/master/rev_link_list_rec.cxx

查找完整代码：https: //github.com/vijaythreadtemp/Data-Structures-And-Algorithms/blob/master/rev_link_list_rec.cxx