递归反转链表

Question

我有一个链表中定义的节点:

typedef struct abc
{
    int id;
    struct abc *next;        
}node;

我想递归地反转一个链表。我将头指针传递给函数。我的函数定义如下：

node *reverseLinkedListRecursively(node *head)
{
    node *current;
    node *rest;
    if(head == NULL)
        return head;

    current=head;
    rest=head->next;

    if(rest == NULL)
    {
       return rest;
    }
    reverseLinkedListRecursively(rest);
    current->next->next=rest;
    current->next=NULL;
    return rest;
}

我该如何继续下去？我已经实现了迭代方法。

- aj983

---

这是作业吗？看起来像作业。如果你想让别人帮助你，那么你应该展示出至少尝试解决问题的努力。 - Cameron Skinner

Answer 1

它应该按照以下方式工作：

node *reverseLinkedListRecursively(node *rest, node *reversed)
{
    node *current;

    if (rest == NULL)
        return reversed;

    current = rest;
    rest = rest->next;
    current->next = reversed;

    return reverseLinkedListRecursively(rest, current);
}

首先，开始使用以下方法：

reverseLinkedListRecursively(linkedList, NULL);

顺便提一下：这个函数是尾递归的。因此，最先进的编译器应该能够将这个递归解决方案转换为更高效的迭代解决方案。

- Codo

---

我不知道为什么我无法思考逻辑......你是如何得出解决方案的......请分享如何提高逻辑思维。 - aj983

工作正常，效率也很高，但并不是很有教育意义，因为它只是将迭代伪装成递归。 - morningstar

Answer 2

node *reverseLinkedListRecursively(node *head)
{
    node *current;
    node *rest;
    if(head == NULL)
        return head;


    current=head;
    rest=head->next;

    if(rest == NULL)
    {
        /* Wrong. Think about the simple case of a one-element list.
           Your code will return NULL as the reversed list. */
        //return rest;
        return current;
    }
    /* You lost the return value, which will be the beginning of the reversed 'rest'. */
    //reverseLinkedListRecursively(rest);
    rest = reverseLinkedListRecursively(rest);

    /* current->next points to the last element in the reversed 'rest'.
       What do you want that to point to? */
    //current->next->next=rest;
    current->next->next = current; // temporarily circular
    current->next=NULL;

    /* Now you can return rest, since you set it to the beginning of the reversed list. */
    return rest;
}

- morningstar

Answer 3

为了递归地反转一个链表，我们递归地反转由除第一个节点以外的所有元素组成的子列表，然后将第一个节点放在末尾。为了将第一个节点放在末尾，我们需要递归调用返回指向最后一个节点的指针，以便可以访问其“next”成员。当子列表为空时，我们停止递归，并返回当前节点。在将第一个节点附加到递归调用结果的末尾后，当我们从当前递归调用返回时，该第一个节点是“最后一个节点”。有一个最后的细节：原来的第一个节点（现在是最后一个）仍然指向原来的第二个节点（现在是倒数第二个）。我们需要将其修正为null，因为它现在是列表的末端。

node* reverseLinkedListHelper(node* head) {
    if (head->next == NULL) { return head; }
    node* last = reverseLinkedListRecursively(head->next);
    last->next = head;
    return head;
}

void reverseLinkedList(node* head) {
    assert (head != NULL);
    reverseLinkedListHelper(head);
    head->next = NULL;
}

还有一个问题需要考虑：我们如何获取指向新链表头的指针？:)

- Karl Knechtel

---

那么我们如何获取指向列表新头部的指针？你能回答吗？你的解决方案必须更改以返回新的头部。 - iHS

Answer 4

对于每次递归，需要记录当前节点和剩余节点的头部。当剩余节点为NULL时返回。在递归返回后，将"rest"的下一个字段翻转，指向当前节点。为了跟踪新的第一个节点，递归函数只需将旧的最后一个节点传回。

void recursive_reverse() {
    // driver for the recursive reverse function.
    // first is a data member of linked list that point to the first node of list.
    first = recursive_reverse(first, first->next);
}

Node* recursive_reverse(Node *current, Node *rest) {
    // if rest == NULL, the current must be the old last node,
    // which is also the new first node
    if (rest == NULL) return current;
    Node *new_first = recursive_reverse(current->next, rest->next);

    // rearrange pointers
    rest->next = current;
    current->next = NULL;

    // pass along the new first node
    return new_first;
}

我的原始实现使用了哨兵节点，因此我没有在这里测试代码。抱歉！只需将其视为伪代码阅读。

- sean_xia

Answer 5

void RecursiveReverse(struct node** headRef)  
{  
    struct node* first;  
    struct node* rest; 

    if (*headRef == NULL) return; // empty list base case

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

    if (rest == NULL) return; // empty rest base case
    RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case after: rest = {3, 2}

    first->next->next = first; // put the first elem on the end of the list
    first->next = NULL; // (tricky step -- make a drawing)

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

- Shekhar Kumar

Answer 6

如果你想要反转一个列表，你必须在你的节点结构中拥有前置节点指针：

typedef struct abc
{
    int id;
    struct abc *next;
    struct abc *prev;        
}node;

而且你的列表必须有指向头和尾的指针：

typedef struct list
{
    node * first;
    node * last;
} list;

- Tio Pepe

---

我在想，我们能否按照我提供的定义来做。 - aj983

看我的回答。不需要改变数据结构就可以做到。 - Codo

在您之前的版本中，我理解您想要在列表中进行反向迭代。 - Tio Pepe

Answer 7

嘿，大家好！下面是反转链表的程序，有递归和非递归两种实现方式。希望这对你们有所帮助。

LINK *reverse_linked_list_recursion(LINK *head)
{
        LINK *temp;
        if (!head) {
                printf("Empty list\n");
                return head;
        }
        else if (!head->next)
                return head;
        temp = reverse_linked_list_recursion(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
}

LINK *reverse_linked_list_without_recursion(LINK *head)
{
        LINK *new, *temp;
        if (!head) {
                printf("No element in the list\n");
                return head;
        }
        else {
                new = head;
                while (head->next) {
                        temp = head->next;
                        head->next = temp->next;
                        temp->next = new;
                        new = temp;
                }
        }
        return new;
}

- Vikunj Singwal