时间戳

首页 > 解决方案 > 用于反转链表的递归代码无法正常工作

java - 用于反转链表的递归代码无法正常工作

问题描述

这里的tail是指向链表最后一个元素的指针。此代码仅在链表中有奇数个节点并显示偶数个节点的错误输出时才有效。请帮助代码中的问题是什么以及它发生的原因？

 public static class Node
 {
    int data;
    Node next;
  }

  public static class LinkedList
  {
    Node head;
    Node tail;
    int size;
    // many other member functions
    
    private void reversePRHelper(Node node , Node prev)
    {
      if(node == null)
      {
        return;
      }
      Node Next = node.next;
      node.next = prev;
      prev = node;
      reversePRHelper(Next , prev);
      
      Node temp = this.head;
      this.head = this.tail;
      this.tail = temp;
      
    }
    public void reversePR()
    {
      reversePRHelper(head,null);
    }
}

标签： javarecursionlinked-list

解决方案

您的代码中的错误是这三行：

Node temp = this.head;
this.head = this.tail;
this.tail = temp;

应该只在最后执行一次，而不是每次递归调用。因此，如果您将这三个语句从您的 reversePrHelper 方法中移到您的 reversePR 方法中，您的代码将起作用。

private void reversePRHelper(Node node , Node prev)
{
  if(node != null)
  {
   return;
  }
  Node Next = node.next;
  node.next = prev;
  prev = node;
  reversePRHelper(Next , prev);
}

public void reversePR()
{
  reversePRHelper(head,null);
  Node temp = this.head;
  this.head = this.tail;
  this.tail = temp;
}

对我来说，不清楚为什么要将尾部保留为属性，因为您无法从尾部导航到任何地方，因为它没有下一个值。如果您的节点也保留对前一个元素的引用，那将是不同的，但它将是一个双链表。

推荐阅读