Alec Livinghouse
Alec Livinghouse

Reputation: 57

Reverse a linked list recursively in java using a temp variable

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
    }

Upvotes: 0

Views: 77

Answers (1)

trincot
trincot

Reputation: 351403

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

Upvotes: 2

Related Questions