在C中以递归方式逆转链表 [英] Reversing a linkedlist recursively in c

问题描述

将head作为参数发送给它时，以下代码可以正常工作.由于我是C语言的新手，所以我不明白它是如何工作的.请帮帮我.

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.

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 

然后将其更改为

4 -> 3 -> 2 -> 1

推荐答案

一般的递归算法是:

1. Divide 2部分中的列表-首先 节点和列表的其余部分.
2. 递归地为rest的 链表.
3. 将rest链接到first.
4. 修复head指针

1. Divide the list in 2 parts - first node and rest of the list.
2. Recursively call reverse for the rest of the linked list.
3. Link rest to first.
4. Fix head pointer

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

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:

_{(来源: geeksforgeeks.org )}

_{(source: geeksforgeeks.org)}
.

这篇关于在C中以递归方式逆转链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！