我仍然在努力使用递归技术来解决问题。我知道有更好的方法可以解决我在下面的反转链表的问题。我见过的大多数方法都是通过使用迭代或递归从头到尾来反转指针。
我试图通过首先递归地找到列表中的最后一个节点，然后在每次函数返回时更改指针来反转列表。
我在下面到底做错了什么？或者这种方法甚至会起作用，而无需将更多参数传递给递归函数？提前感谢您的帮助。
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;
}
我不会给你代码，我会给你想法。您可以在代码中实现该想法。
所有递归问题的关键是找出两种情况：重复步骤和结束情况。一旦你这样做了，它几乎就像神奇地工作一样。
将此原则应用于反转链表：
- 结束情况：一个元素的列表已经反转(这很简单(并返回元素本身
- 重复情况：给定列表 L，反转此最小意味着反转 L'，其中 L' 是没有第一个元素的列表(通常称为
head(，而不是添加 head 作为列表的最后一个元素。返回值将与刚刚进行的递归调用的返回值相同。
这是可以做到的。理解递归的关键是起点是什么？
通常我创建一个"启动">函数来准备第一次调用。有时它是一个单独的函数(如底部的非 OO 影响(。有时它只是一个特殊的第一次调用(如下例所示(。
同样关键是在变量发生变化之前记住变量以及new head是什么。
新head是列表的最后一个元素。所以你必须从列表的底部得到它。
next元素始终是您的父元素。
然后诀窍是按照正确的顺序做所有事情。
Node* Reverse( Node* parent) // Member function of Node.
{
Node* new_head = next ? next->Reverse( this )
: this;
next = parent;
return new_head;
}
调用函数的方式是：var.Reverse( nullptr);
例：
int main()
{
Node d{ 4, nullptr };
Node c{ 3, &d };
Node b{ 2, &c };
Node a{ 1, &b };
Node* reversed = a.Reverse( nullptr );
}
那么这里发生了什么？
首先，我们创建一个链表：
a->b->c->d->nullptr
然后函数调用：
a.Reverse(nullptr)被称为。- 这会使用父节点调用下一个节点
b.Reversea上的Reverse。 - 这会使用父节点调用下一个节点
bc.Reverse上的Reverse。 - 这会使用父节点调用下一个节点
d.Reversec上的Reverse。 d没有next节点，所以它说新的头是它自己。d的next现在是它的父cd返回自身作为new_head。- 回到
c：new_head从d返回d c的next现在是它的父bc返回从d收到的new_head- 回到
b：new_head从c返回d b的next现在是它的父ab返回从c接收new_head- 回到
a：new_head从b返回d a的next现在是它的父nullptra返回它从b收到的new_head- 返回
d
非面向对象实现;
Node* reverse_impl(Node* parent)
{
Node* curr = parent->next;
Node* next = curr->next;
Node* new_head = next ? reverse_impl( curr )
: curr;
curr->next = parent;
return new_head;
}
Node* reverse(Node* start)
{
if ( !start )
return nullptr;
Node* new_head = reverse_impl( start );
start->next = nullptr;
return new_head;
}
这是我在 5 分钟内编写的完整实现：
#include <stdio.h>
struct Node
{
int data;
struct Node *next;
};
struct Node* Reverse(struct Node *n)
{
static struct Node *first = NULL;
if(first == NULL)
first = n;
// reached last node in the list
if (n->next == NULL)
return n;
Reverse(n->next)->next = n;
if(n == first)
{
n->next = NULL;
first = NULL;
}
return n;
}
void linked_list_walk(struct Node* n)
{
printf("%d", n->data);
if(n->next)
linked_list_walk(n->next);
else
printf("n");
}
int main()
{
struct Node n[10];
int i;
for(i=0;i<10;i++)
{
n[i].data = i;
n[i].next = n + i + 1;
}
n[9].next = NULL;
linked_list_walk(n);
Reverse(n);
linked_list_walk(n+9);
}
输出：
0123456789
9876543210