java - 交换链表节点后递归 toString 函数的堆栈溢出

Question

交换头节点和链表中间的另一个节点后，在链表上使用递归 toString 函数时，出现堆栈溢出。我不确定为什么会发生这种情况，希望我能得到一些有关实际情况的指导。看起来在我的交换函数执行之前，toString 工作得完全正常，但是一旦我交换节点，我的递归 toString 函数就会碰巧出现堆栈溢出错误。

我的链接列表类:

public class LinkedList {
    //
    //Instance variable
    //
    private Node top;

    //
    //Instance and static methods below
    //

    //Accessor for the top Node
    public Node getTop() {
        return top;
    }

    public Node getPreviousNode(Node toFind) {
        //call getPreviousNodeRec() method
        if (top.equals(toFind))
            return null;
        else
            return getPreviousNodeRec(top, toFind);
    }

    private Node getPreviousNodeRec(Node start, Node toFind) {
        if (start.getLink().equals(toFind)) {
            return start;
        } else
            return getPreviousNodeRec(start.getLink(),toFind);
    }

    public void swap(Node n1, Node n2) {
        if (top.equals(n1)) {
            System.out.println("top equals n1");
            Node n2prev = getPreviousNode(n2);
            Node temp = n2.getLink();

            top = n2;
            top.setLink(n1.getLink());
            n1.setLink(temp);
            n2prev.setLink(n1);

            System.out.println("complete");
        }
    }

    public String toString() {
        if (top == null)
            return "There is nothing in the list!";
        else {
            String value = "";
            return toStringRec(top, value);
        }
    }

    private String toStringRec(Node start, String value) {
        if (start.getLink() != null) {
            value += start.getData()+"\n";
            return toStringRec(start.getLink(),value);
        } else
            return value+start.getData();
    }

    public void setTop(Node top) {
        this.top = top;
    }
}

现在我只是想测试一种情况下的交换方法(top = n1)。

这是我的主要方法:

public static void main (String[] args) {
    //Testing the getPreviousNode method
    LinkedList myList = new LinkedList();

    myList.add(-700);
    myList.add("hello");
    myList.add(12);
    myList.add(55);
    myList.add(13000);
    myList.add("world");
    myList.add("pizza");
    myList.add(870);

    System.out.println("The previous node of the node containing 12 is the Node containing \"hello\":");

    System.out.println(myList.getPreviousNode(
         myList.getTop().getLink().getLink()).getData());
    System.out.println();

    //Testing swap:
    System.out.println("The initial list is:");
    System.out.println(myList);

    System.out.println();
    System.out.println("Now swapping the first and second nodes, and the result is:");
    myList.swap(myList.getTop(), myList.getTop().getLink());
    System.out.println(myList);
}

Answer 1

如果 n1 和 n2 相距 2 个节点，则您的方法有效，在它们彼此相邻的情况下，就像在您执行此行的示例中一样:

top.setLink(n1.getLink());

您正在将 n2 链接指向其自身。 您需要检查 n1 和 n2 是否指向 top 到 n2、n1.link 到 n2.link和n2.link到n1。