c++ - 使用递归从尾部开始反转链表

Question

我仍在努力使用递归技术来解决问题。我知道有更好的方法可以解决下面反转链表的问题。我见过的大多数方法都是通过使用迭代或递归从头到尾来反转指针。

我试图通过首先递归地找到列表中的最后一个节点然后在每次函数返回时更改指针来反转列表。

下面我到底做错了什么？或者这种方法甚至可以工作，而不需要将更多参数传递给递归函数？预先感谢您的帮助。

struct Node
{
    int data;
    struct Node *next;
};

Node* Reverse(Node *head)
{
    static Node* firstNode = head;
    // if no list return head
    if (head == NULL)
    {
        return head;
    }

    Node* prev = NULL;
    Node* cur = head;

    // reached last node in the list, return head
    if (cur->next == NULL)
    {
        head = cur;
        return head;
    }

    prev = cur;
    cur = cur->next;
    Reverse(cur)->next = prev;

    if (cur == firstNode)
    {
        cur->next = NULL;
        return head;
    }
    return cur;
}

编辑:另一次尝试

Node* ReverseFromTail(Node* prev, Node* cur, Node** head);

Node* ReverseInit(Node** head)
{
    Node* newHead = ReverseFromTail(*head, *head, head);
    return newHead;
}



Node* ReverseFromTail(Node* prev, Node* cur, Node** head)
{
    static int counter = 0;
    counter++;

    // If not a valid list, return head
    if (head == NULL)
    {
        return *head;
    }

    // Reached end of list, start reversing pointers
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }


    Node* retNode = ReverseFromTail(cur, cur->next, head);
    retNode->next = cur;


    // Just to force termination of recursion when it should. Not a permanent solution 
    if (counter == 3)
    {
        cur->next = NULL;
        return *head;
    }

    return retNode;
}

终于解决了:

Node* NewestReverseInit(Node* head)
{
    // Invalid List, return
    if (!head)
    {
        return head;
    }

    Node* headNode = NewestReverse(head, head, &head);

    return headNode;
}

Node* NewestReverse(Node *cur, Node* prev, Node** head)
{
    // reached last node in the list, set new head and return
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }

    NewestReverse(cur->next, cur, head)->next = cur;

    // Returned to the first node where cur = prev from initial call
    if (cur == prev)
    {
        cur->next = NULL;
        return *head;
    }

    return cur;
}

Answer 1

我不会给你代码，我会给你思路。您可以在代码中实现这个想法。

所有递归问题的关键是找出两种情况:重复步骤和结束情况。执行此操作后，它就像变魔术一样有效。

将这个原则应用于反转链表:

• 结束案例:一个元素的列表已经被反转(这很简单)并返回元素本身
• 重复情况:给定列表 L，反转这个最少意味着反转 L'，其中 L' 是 L' 是没有第一个元素(通常称为 head)的列表，而不是添加head 作为列表的最后一个元素。返回值将与您刚刚进行的递归调用的返回值相同。