0

因此，作为计算机编程课程的一部分，我根据此算法反转了一个单链节点列表

“依次遍历链表，取出每个节点，作为新的第一个节点插入。”

我能够迭代地做到这一点，但现在我的教授希望我们递归地做到这一点。我正在尽我所能理解递归，但它不是很好。

因此，我将我的编码从迭代更改为我认为是递归的

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()确实有效，但我只是不知道我是否实现了递归。

4

5 回答 5

1

在编写递归时，通常最好考虑结束情况，然后最后编写递归情况。关于递归的另一件事是返回结果非常有用。

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

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

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);
        } 
    }

}

享受！

于 2012-11-17T05:59:20.130 回答
0

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;

 }

请给我你的建议...

于 2013-05-08T06:38:30.523 回答
0

这个怎么样：

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);
}

短而甜。

于 2013-10-15T20:36:20.403 回答
0

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

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;     
}
于 2014-02-08T17:16:33.980 回答
0

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 对于每个内部调用都是本地的。在 stackeach time 函数调用自身时，现在在堆栈上创建的两个临时指针 *first 是链表的最前面的元素，而 *rest 是指向链表上的下一个元素的指针。在每个调用中，网络传递给递归意味着第二个元素指针被传递。最后，如果(rest == NULL)堆栈展开在堆栈展开中开始，则没有剩余元素。在堆栈展开中 *rest forward 将指向低级 *first 指针，这只是在展开期间将指针从一个堆栈反转到另一个堆栈。在最初的 *first 成为最后一个元素，因此它的 next 被更改为 null 以防止非法引用first->next = NULL

于 2014-04-19T21:29:33.627 回答