Reversing a Linked List not working as expected

mohelt

I am currently trying to reverse a linked list, I have an unexpected problem where it doesn't print correctly. And when I try and access the values of the linked list I get an error. I would greatly appreciate an expert eye to see what I am missing. Thanks in advance.

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();
    }

The reverse Linked List method:

    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;
    }

The main method:

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());
    }

The output:

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

As you are mutating ("rewiring") the given linked list in the reverseLinkedList function, you are not actually producing a new linked list. So to have it return something is actually contradictory. Either it should return a completely new linked list without mutating the given one, or it should mutate the given linked list and not return anything.

From your main code I see that you actually expect to mutate the given linked list, as you don't use the returned value and print the result based on sll. So make your function a void one, and drop the return statement.

The core problem now is that you never change the head member: it still references what used to be the first node in the list, but is now the last one. You should assign the node to head that previously was the tail node.

So the last statement in your function should be:

sll.head = previous;

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related