递归地反转单链表

Question

因此，作为计算机编程课程的一部分，我将基于此算法反转一个单独链接的节点列表

"按顺序遍历列表，删除每个节点并将其作为新的第一个节点插入。">

我本来可以迭代地做这件事，但现在我的教授希望我们递归地做。我正在尽我所能理解递归，但它的效果不太好。

所以，我把我的编码从迭代改为我认为递归的

private void recursiveReverse2(Node p)
{
Node lead = p;
Node tail = p;
if (p == null)
{
return;
}
if (p.next == null)
{
return;
}
current = tail.next;
lead = current.next;
current.next = null;
tail.next = lead;
current.next = head;
head = current;
recursiveReverse2(tail);
}

public void reverse2()
{
toggle();   //swithces sort of list from ascending-descending
recursiveReverse2(head); //head initialized at start of class
}

基本上，我想问我所做的是否真的是递归。因为，recursiveReverse2()确实有效，但我只是不知道我是否实现了递归。

Answer 1

在编写递归时，通常最好考虑结束情况，然后最后编写递归情况。递归的另一个特点是它在返回结果时非常有用。

是的，您的解决方案在技术上是递归的，但我认为代码不起作用。在current.next = head行，没有定义head，除非此代码在您尚未显示的某个类中。更糟糕的是，它可能是无限循环，因为在函数的开头，tail = p和结尾，递归是用tail调用的，因此是无限循环。这最多会反转长度为3的列表，但不会反转任何长度的列表。

在Java中，递归函数通常需要一个"helper"函数来启动它。首先，假设以下节点类：

public class Node{
public object data;
public Node next;
}

考虑到问题陈述，我假设我们不允许玩数据指针，只允许玩下一个指针。此代码将是Node之外的其他类。

public Node recursiveReverse(Node p)
{
return helperReverse(p, null);
} 
private Node helperReverse(Node p, Node previous)
{
if (p == null)
{
return p;
}
else if (p.next == null)
{
p.next == previous;
return p;
}
else
{
Node next = p.next;
p.next = previous;
return helperReverse(next, p);
}
}

如果它被合并到Node类中，它会变得更好。

public class Node{
public object data;
public Node next;
public Node reverse() {
return reverse1(null);
} 
private Node reverse1(Node previous) {
if (next == null) {
next == previous;
return this;
}
else {
Node other = next;
next = previous;
return reverse1(other, this);
} 
}
}

享受吧！

Answer 2

C++中的递归代码，假设您有一个节点类，它有下一个指针。。。。两个函数，第一个调用递归函数，第二个递归函数反转单链表

void callReverse()
{
node *tempPointer=head;
head=NULL;
reverse(tempPointer);
}

第二个函数是递归函数

void reverse(node * pointer)
{
if(pointer->next==NULL)   //this case works only when linked list has a single node
{
if(head==NULL)
head=pointer; 
}
else if(pointer->next->next!=NULL)
{
reverse(pointer->next)  //recursive call
}
if(head==NULL)
head=pointer->next;
pointer->next->next=pointer;
pointer->next=NULL;
}

请给我你的建议。。。

Answer 3

这个怎么样：

void driver(Node head)
{
rec_rev_ll(head,NULL); 
}
void rec_rev_ll(Node head, Node prev) 
{
Node tmp = head->next;
if(tmp == NULL) // Ends recursion when end of linked list is reached.
{
head->next = prev;
return;
}
head->next = prev;
rec_rev_ll(tmp,head);
}

又短又甜。

Answer 4

在不使用任何临时节点的情况下反转列表：

struct node* reverse_helper(struct node *ptr, struct node **head)
{
if(ptr->next == NULL)
*head = ptr;
else 
(reverse(ptr->next,head))->next = ptr;
return ptr;
}        
/*Call reverseList Function with your List head reference */
void reverseList(struct node **head)
{
struct node *ptr = reverse_helper(*head,head);
ptr->next = NULL;     
}

Answer 5

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;             

}

解释

这里，指针first和next对于每个interanl调用都是本地的。在stackeach时间函数调用本身上，现在在stack上创建的两个临时指针*first是链表的front元素，而*rest是指向链表上下一个元素的指针。在每次调用中，网被传递给递归意味着第二个元素指针被传递。如果(rest == NULL)堆栈展开在堆栈展开中开始，则在没有剩余元素时结束。在堆栈中展开*rest forward将指向低位*第一个指针，这只是在展开期间将指针从一个堆栈反转到另一个堆栈。在最初的*first变成最后一个elemnt，所以它的next被更改为null以防止非法引用first->next = NULL