递归地将堆栈转换为链表

所以我一直在做一个编程任务，涉及到大小约13,000的堆栈实现并将其转换为链表。该指南基本上是通过顺序扫描链表来填充堆栈（IE尾部将是堆栈的顶部），并且您希望使用堆栈重新创建链接列表。诀窍是你必须使用递归方法来做到这一点。这个栈类中唯一的方法是pop（返回并移除顶层元素）和isEmpty（告诉栈是否为空）。我有代码完成工作，但它需要增加java堆栈大小（否则我得到StackOverflowError），我觉得这是不被允许的。递归地将堆栈转换为链表

这是说有没有人知道一种方式，我可能会得到这个工作，而不增加java堆栈大小。

堆栈是一个静态字段，我标记为S.头是什么应该是链接列表中的第一个节点，而steper只是一个用于创建其他每个步骤的节点。

这里是我目前拥有的代码：

public static void stackToList() 
{ 
    int x = 0; 
     if(S.isEmpty()) 
     { 
      return; 
     } 
     x = S.pop(); 
     stackToList(); 
     if (head == null) 
     { 
      head = new ListNode(x, null); 
      steper = head; 
     } 
     else 
     { 
      steper.next = new ListNode(x, null); 
      steper = steper.next; 
     } 

}

谢谢你的时间提前任何帮助。

来源

2016-09-30 xtruexwolfx

出于好奇，堆栈里有什么？ – leigero

只是很多整数。没有什么花哨的。 – xtruexwolfx

只是为了澄清，当你说“堆栈大小”是否在递归调用期间引用Java调用堆栈？因为如果你正在阅读它，你的'S'不会增加！ – EvenPrime

发生这种情况是因为您要在内存堆栈中保留整个函数调用列表。您只有在到达堆栈底部后才开始创建链接列表，从而保持以前的所有调用stackList等待结束。

您需要开始创建您的链接列表与第一个弹出的堆栈。

简单& 非测试（在Java中没有工作在很长一段时间了）函数可能看起来像：

public static ListNode stackToList(ListNode head) { 
    if(S.isEmpty()) 
     return head; 

    int stackValue = S.pop(); 
    ListNode node = ListNode(stackValue, null); 
    node.next(head); 
    return stackToList(node); 
}

而你把它想：

ListNode head = stackToList(null)

HTH

编辑：现在我发布了它，我意识到我的代码有可能与您的问题相同，因为我记得Java doesn't support tail-call optimization。

来源

2016-09-30 13:27:20

对不起，我在学校的反应很慢。只要创建相同的列表，您的代码就可以正常工作，但它也会遇到堆栈溢出。在这一点上，我只是将它包装在一个try catch中，以便catch再次调用该方法。显然，这远非理想，但教授现在明确表示我们不能增加Java堆栈的大小，所以我对如何期待我们解决它的方式感到不知所措。 – xtruexwolfx

这不，如果你正在使用java.util.LinkedList和java.util.Stack但因为你没有提供，我将使用那些在我下面的例子解决这些对象的代码从你的问题十分清楚：

public static void main(String[] args) { 
    //Create a stack 
    Stack<Integer> stack = new Stack<Integer>(); 
    stack.push(0); 
    stack.push(1); 
    stack.push(2); 
    stack.push(3); 
    stack.push(4); 
    stack.push(5); 
    stack.push(6); 
    stack.push(7); 
    stack.push(8); 
    stack.push(9); 

    //Create a list to hold your stack elements 
    LinkedList<Integer> linkedList = new LinkedList<Integer>(); 

    //Call the conversion method, which modifies both the stack and the list 
    convertStackToLinkedList(stack, linkedList); 

    //print the results 
    System.out.println("linkedList: "+linkedList); 
} 

public static void convertStackToLinkedList(Stack<Integer> stack, LinkedList<Integer> linkedList){ 
    int topStackElement = stack.pop(); 
    linkedList.add(0,topStackElement); 
    if(!stack.isEmpty()) 
     convertStackToLinkedList(stack, linkedList); 
}

我怀疑你可能没有使用java.util.LinkedList，因为你的代码试图修改列表的内部。因此，您只需实现类似java.util.LinkedList类中的add(int index, E element)方法的方法，然后在递归中使用它。我假设你可以做到这一点，如果你有权访问列表的内部。

编辑：

我忘了提及，我在这个答案由恶劣古普塔同意你看到StackOverflowError的原因是，你在等待，直到你达到你的递归的终点修改你的清单。在一些递归中，你必须等到最后，但如果你不必等，就不要这样做。

来源

2016-09-30 14:07:47

递归地将堆栈转换为链表

回答

相关问题