使用C中的递归来反转链表

I was trying the reversal of a linked list using recursion. I viewed the sample program in geeksforgeeks website. They had a good explanation. But I could not understand what the *headref will hold on every stack unwinding. Doesnt it hold the next address during every stack unwinding, if its that way then how does the rest value is same during all the stack unwinding calls. The first value gets changed during the stack unwinding and so is the rest value. Why doesnt rest value is not changed when the first value is changed for every stack unwinding. Please help to understand.

我正在尝试使用递归来反转链表。我在geeksforgeeks网站上查看了示例程序。他们有一个很好的解释。但是我无法理解每个堆栈展开时* headref会保持什么。在每次堆栈展开期间它是否保持下一个地址,如果是这样的话,那么在所有堆栈展开调用期间其余值是如何相同的。堆栈展开期间第一个值会发生变化,其余值也会变化。为每个堆栈展开更改第一个值时,为什么不会更改静止值。请帮忙理解。

void recursiveReverse(struct node** head_ref)
{
    struct node* first;
    struct node* rest;

    /* empty list */
    if (*head_ref == NULL)
       return;  

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref; 
    rest  = first->next;

    /* List has only one node */
    if (rest == NULL)
       return;  

    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first; 

    /* tricky step -- see the diagram */
    first->next  = NULL;         

    /* fix the head pointer */
    *head_ref = rest;             
}

3 个解决方案

#1

Once the 'rest list' got reversed in the recursive step, its first item, pointed at by rest, became its last item, so the previous 'first' gets appended after that. Then it is the last item, so its next member becomes NULL. Finally we return the new head through the call parameter.

一旦“休息列表”在递归步骤中被反转,其第一个项目(由休息指向)就成为它的最后一个项目,因此之后的“第一个”将被附加。然后它是最后一项,因此它的下一个成员变为NULL。最后,我们通过call参数返回新头。

#2

The head is changed in every recursive call.

每次递归调用都会更改头部。

Each recursive call takes the sublist [k,n] , where k is the previously parsed elements.

每个递归调用都采用子列表[k,n],其中k是先前解析的元素。

The first entry is [0,n] , which in the code above is [first,rest] .

第一个条目是[0,n],在上面的代码中是[first,rest]。

Initially links are from first to rest. Before each recursive call rest gets linked to first having a temporary loop inside the list (first points to rest, rest points to first).

最初链接从第一个到休息。在每个递归调用休息之前,链接到首先在列表中有一个临时循环(首先指向休息,休息指向第一个)。

Then , after the recursive call returns, the loop is killed by removing the first to rest link and putting first to be rest's next . (basically keeping only the inverse order).

然后,在递归调用返回之后,通过删除第一个到休息链接并将第一个放在休息的下一个循环来终止循环。 (基本上只保持相反的顺序)。

As any single linked list, the last element needs to have no childern, and right now first is the last element, so first->next becomes null.

作为任何单个链表,最后一个元素不需要childern,现在首先是最后一个元素,所以first-> next变为null。

The new head of the list is the last element, which in this case will be rest , which gets passed on from the deepest recursion upwards.

列表的新头是最后一个元素,在这种情况下将是休息,它从最深的递归向上传递。

This algorithm is so much faster and easier to implement with an iterative approach.

使用迭代方法,此算法更快,更容易实现。

#3

Problem of such algorithm is memory consumption required by recursive calls.

这种算法的问题是递归调用所需的内存消耗。

You have one parameter pointer and two var pointer, each call that goes on top of the memory stack. But it is the reason it works and the var is not changed. It does not reference the same memory area.

你有一个参数指针和两个var指针,每个调用都在内存堆栈的顶部。但这是它工作的原因,并且var没有改变。它不引用相同的内存区域。

You can note that an iterative approch is faster and easier in fact.

您可以注意到迭代的approch实际上更快更容易。

void iterativeReverse(struct node** head_ref) {
    struct node *prev=NULL, *next;
    while (*head_ref) {
       next=*head_ref->next;
       *head_ref->next=prev;
       prev=*head_ref;
       *head_ref=next;
    }
    *head_ref=prev;
}

#1

#2