Reverse a linked list recursively in java using a temp variable

Question

I implemented a solution to reverse a linked list in java that I found online. But it is not working in my code for some reason.

When I print the list it only prints the first node. I know the print method works because it prints the whole thing when I don't try to reverse.

Where did I go wrong in this code?

public class LinkedLists {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addLast(10);
        list.addLast(20);
        list.addLast(30);
        list.reverseList();
        list.print();
    }
    
    
    public static class LinkedList{
        private class Node{
            private int value;
            private Node next;
        }
            public Node first;
            public Node last;
    
    public void addLast(int item){
        Node node = new Node();
        node.value = item;
            if(first == null) {
                first = node;
                last = node;
                } else {
                last.next = node;
                last = node;
                }
            }
            private Node reverse(Node head, Node newHead) {
                //base case: when first = last you return
                if(head == null) {
                    return newHead;
                }
                Node temp = head.next;
                head.next = newHead; //this will initially be null
                newHead = head;
                head = temp;
                return reverse(head, newHead);
            }
            
            public Node reverseList() {
                return reverse(first, null);
            }
            
            public void print(){
                Node current = first;
                while (current != null){
                    System.out.print(current.value + " ");
                    current = current.next;
                } 
            }
        } //class ends
    }

Your reverse algorithm never touches the important members first and last, yet your print method starts at first (which was the first and is presumably now last). — user2740650
– user2740650, Commented Oct 3, 2020 at 1:14
As a value, yes. But that doesn't mean that first and last are being updated. Naturally if you've reversed a list, those would need to be swapped. The reason you only see one value printed is because first is pointing at the last entry, after the reversal. — user2740650
– user2740650, Commented Oct 3, 2020 at 2:30

trincot · Accepted Answer · 2020-10-03 13:28:55Z

2

Although reverse returns the correct reference for the new head, the initial call of reverseList -- in the main program -- ignores this returned reference.

Your reverseList method should better not return anything, but instead update the first and last members:

public void reverseList() {
    last = first;
    first = reverse(first, null);
}

answered Oct 3, 2020 at 13:28

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Reverse a linked list recursively in java using a temp variable

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related