Java 反转链接列表——调试器甚至无法工作

Question

所以基本上我创建了自己的 linkedlist 类，现在我添加了一个名为 reverse 的函数来反转它。奇怪的是，它不起作用，我什至无法调试!我不知道发生了什么，如果有人可以提取我的代码并让我知道发生了什么，那就太棒了。我的 Node 类和 LinkedList 类都在一个文件中，反向函数称为反向。如果您现在尝试使用反向，它不起作用，会卡住调试器，甚至不允许我在第一次迭代后单步执行 while 循环。 (我正在使用 IntelliJ)

class Node<Type> {

    private Type data;
    private Node<Type> nextNode;

    public Node(Type data) {
        this.data = data;
    }

    public void setData(Type data) {
        this.data = data;
    }

    public Type getData(){
        return data;
    }

    public void setNextNode(Node<Type> nextNode) {
        this.nextNode = nextNode;
    }

    public Node<Type> getNextNode() {
        return nextNode;
    }

    @Override
    public String toString(){
        return "Data: " + this.data;
    }
}

public class LinkedList<Type> {

    private Node<Type> head; 
    private int length; 

    public LinkedList() {
        length = 0;
    }

    // Returns: Pointer to the first Node in the list where Node.getData().equals(data)
    // O(N)
    public Node<Type> find(Type data) {
        Node<Type> currentNode = head; 
        while(currentNode != null) {
            if(currentNode.getData().equals(data)) {
                return currentNode;
            }
            currentNode = currentNode.getNextNode();
        }

        return null;
    }


    // Returns: the length of the list
    // O(1) 
    public int getLength() {
        return length; 
    }

    // Create a node with data and add it to the front of the list
    // O(1)
    public void addAtHead(Type data) {
        Node<Type> newHead = new Node<Type>(data);
        newHead.setNextNode(this.head);
        this.head = newHead;
        length += 1;
    }

    // Delete the head node (garbage collection)
    // O(1)
    public void deleteHead(){
        if(this.head != null) {
            this.head = this.head.getNextNode();
            length -= 1;            
        }
    }

    public void reverse() {
        Node<Type> rememberMe = head.getNextNode();

        while(rememberMe != null) {
            Node<Type> temp = head;
            head = rememberMe;
            rememberMe = head.getNextNode();
            head.setNextNode(temp);
        }
    }

    // Print out the node using node.toString
    // Eg. { node1.toString() , node2.toString() , node3.toString() }
    // O(N)
    @Override
    public String toString(){
        String result = "{";
        Node<Type> currentNode = this.head; 
        while(currentNode != null) {
            result += " " + currentNode.toString() + " ";
            currentNode = currentNode.getNextNode();
            if(currentNode != null) {
                result += ", ";
            }

        }

        result += "}";

        return result;
    }
}

Answer 1

反转后，原始头部仍然有一个下一个指向第二个元素，但现在是倒数第二个，因此反转后，末尾有一个循环。这意味着 toString() 函数中有一个无限循环，intellij 调试器可能正在调用该循环。

要修复此问题，请跟踪原始头部并将其 next 设置为 null。

public void reverse() {
    Node<Type> orig_head = head;
    Node<Type> rememberMe = head.getNextNode();

    while(rememberMe != null) {
        Node<Type> temp = head;
        head = rememberMe;
        rememberMe = head.getNextNode();
        head.setNextNode(temp);
    }
    orig_head.setNextNode(null);
}