recursion - 递归地将堆栈转换为链表

Question

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

话虽如此，是否有人知道我可以在不增加 java 堆栈大小的情况下使其工作的方法。

堆栈是我标记为 S 的静态字段。 Head 应该是链表中的第一个节点，而 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;
        }

}

提前感谢您的任何帮助。

Answer 1

发生这种情况是因为您在内存堆栈中保留了完整的函数调用列表。只有在到达堆栈底部后才开始创建链表，从而保留之前对 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 .