反转链接列表未按预期工作

Question

我目前正在尝试反转链表，但遇到无法正确打印的意外问题。当我尝试访问链接列表的值时，出现错误。我将不胜感激专家的眼睛，看看我错过了什么。提前致谢。

public class SinglyLinkedList<E> implements Cloneable, Iterable<E>, List<E> {
    //---------------- nested Node class ----------------

    /**
     * Node of a singly linked list, which stores a reference to its
     * element and to the subsequent node in the list (or null if this
     * is the last node).
     */
    private static class Node<E> {
        private E data;  // reference to the element stored at this node

        private Node<E> nextNode; 

        
        //methods for accessing variables

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

        public E getData() { return data; }

        // Modifier methods
        public void setNext(Node<E> n) { nextNode = n; }
        public void setData(E n) { data = n; }
        public Node(E e, Node<E> n) {
            nextNode = n;
            data = e;
        }

        // reference to the subsequent node in the list// TODO
    } //----------- end of nested Node class -----------

    // instance variables of the SinglyLinkedList
    private int size = 0; // number of nodes in the list
    private Node<E> head = null; // head node of the list (or null if empty)

    public SinglyLinkedList() {
    }              // constructs an initially empty list

    // access methods

    /**
     * Returns the number of elements in the linked list.
     *
     * @return number of elements in the linked list
     */
public void addFirst(E e) {
        head = new Node<E>(e, head); // create the new node and link new node
        size++;
    }
    /**
     * Produces a string representation of the contents of the list.
     * This exists for debugging purposes only.
     */
    public String toString() {
        StringBuilder temporaryString = new StringBuilder();
        temporaryString.append("[");
        for(Iterator<E> iterator = iterator(); iterator.hasNext();){
            temporaryString.append(iterator.next()).append(", ");
        }
        temporaryString.deleteCharAt(temporaryString.length() - 1);
        temporaryString.deleteCharAt(temporaryString.length() - 1);
        temporaryString.append("]");
        return temporaryString.toString();
    }

    private class SinglyLinkedListIterator implements Iterator<E> {
        private Node<E> current;
        public SinglyLinkedListIterator() {
            current = head;
        }
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public E next() {
            if(!hasNext()) throw new RuntimeException("No such element");

            E res = current.getData();
            current = current.getNextNode();
            return res;
        }
    }

    public Iterator<E> iterator() {
        return new SinglyLinkedListIterator();
    }

反向链表法：

    public Node<E> reverseLinkedList(SinglyLinkedList sll) {
        Node<E> previous = null;
        Node<E> current = sll.head;
        while (current != null) {
            Node<E> nextElement = current.getNextNode();
            current.setNext(previous);
            previous = current;
            current = nextElement;
        }
        return previous;
    }

主要方法：

public static void main(String[] args) {
        SinglyLinkedList<Integer> sll2 = new SinglyLinkedList<Integer>();
        sll2.addFirst(1);
        sll2.addFirst(2);
        sll2.addFirst(3);

System.out.println(sll2.toString());
        sll2.reverseLinkedList(sll2);
System.out.println(sll2.toString());
    }

输出：

[3, 2, 1]
//i should expect to get 1,2,3
[3]

Answer 1

当您在变异（“重新布线”） reverseLinkedList 函数中给定的链表时，您实际上并没有生成新的链表。所以要有它 return 东西其实是矛盾的。要么它应该 return 一个全新的链表而不改变给定的链表，或者它应该改变给定的链表而不是 return 任何东西。

从你的 main 代码中我看到你实际上希望改变给定的链表，因为你不使用 returned 值并根据 sll 打印结果。所以让你的函数成为 void 一个，然后删除 return 语句。

现在的核心问题是您永远不会更改 head 成员：它仍然引用以前是列表中第一个节点但现在是最后一个的节点。您应该将节点分配给之前作为尾节点的 head。

所以函数中的最后一条语句应该是：

sll.head = previous;

反转链接列表未按预期工作

Reversing a Linked List not working as expected

java

linked-list

singly-linked-list