递归链表。我究竟做错了什么？

public class Reverse {

  public static void printLL(Node head) {
      while(head!=null){
          System.out.print(head.getData()+"-->");
          head=head.next;
      }
  }

  public static Node reverseLL(Node head){
      if(head == null) {
          return head;
      }
      return reverseLL(head.next);
  }

  public static void main(String[] args) {
      Node first=new Node(10);
      Node head=first;
      Node second=new Node(20);
      first.next=second;
      Node third=new Node(30);
      second.next=third;
      Node fourth=new Node(40);
      third.next=fourth;
      printLL(head);
      System.out.println("\nReverse of Linked List is \n");
      head=reverseLL(head);
      printLL(head);
   }
}

Here is my code. It is not printing anything.

这是我的代码。它不打印任何东西。

I think that due to recursion, it is pointing to the null pointer and hence no data is present at null position.

我认为由于递归,它指向空指针,因此在null位置不存在数据。

Please tell me what can I do to make the code correct.

请告诉我如何才能使代码正确无误。

Thanks in advance

提前致谢

3 个解决方案

#1

Your reverseLL simply goes through all the Nodes and when it reaches the last one doing if(head==null), null is returned.

你的reverseLL只是通过所有节点,当它到达最后一个if(head == null)时,返回null。

You need to fix the reverseLL function. Try adding traces into the function to understand what it does step by step.

您需要修复reverseLL功能。尝试在函数中添加跟踪以逐步了解它的功能。

#2

You seemn to have missed a crucial point about recursion - you have to call yourself.

你似乎没有错过关于递归的关键点 - 你必须给自己打电话。

I will suggest a change to printLL that should demonstrate one possible recursive solution that should work.

我将建议对printLL进行更改,该更改应该演示一个可行的递归解决方案。

public static void printLL(Node head) {

    if (head != null) {
        System.out.print(head.getData() + "-->");
        printLL(head.next);
    }
}

Note how the code basically says if there is a head, print it's data and then print it's head.next.

注意代码如何基本上说如果有一个头,打印它的数据,然后打印它的head.next。

#3

The problem is that your reverseLL does not do anything to the head after calling itself recursively.

问题是你的reverseLL在递归调用之后对头部没有任何作用。

The base case is right: when head is null, you return null. The recursive step, however, is not complete: you need to reverse the rest of the list, but then you have to attach it back to the head.

基本情况是正确的:当head为null时,返回null。然而,递归步骤并不完整:您需要反转列表的其余部分,但是您必须将其附加回头部。

The simplest way to accomplish this is to pass an extra parameter for the prior node, so that you could do

完成此操作的最简单方法是为先前节点传递额外参数,以便您可以执行此操作

head.next = prior;

inside your recursive method. Here is how your "wrapper" method would look:

在你的递归方法里面。以下是“包装”方法的外观:

public static Node reverseLL(Node head) {
    if(head==null){
        return null;
    }
    return reverseLL(head, null);
}

Note that it is not recursive - all it does is calling a two-argument overload.

请注意,它不是递归的 - 它只是调用两个参数的重载。

The recursive method knows that head is never null, so its base case is head.next == null:

递归方法知道head永远不会为null,所以它的基本情况是head.next == null:

public static Node reverseLL(Node head, Node prior) {
    Node res;
    if (head.next == null) {
        res = head;
    } else {
        res = reverseLL(head.next, head);
    }
    head.next = prior;
    return res;
}

The reversal of the head node is done in the assignment prior to the return. Note how the method returns the last non-null node in the chain.

头节点的反转是在返回之前的分配中完成的。请注意该方法如何返回链中的最后一个非空节点。

Demo

#1