compiler won't advance in recursive reversal of singly linked list

Question

I have a recursive static method inside a SinglyLinkedList class which runs forever for an undetermined reason. This class is generic and its declaration looks like this:

public class SinglyLinkedList<E>{

This class has an inner generic class Node which looks like this:

private static class Node<E> {
    private E element;
    private Node<E> next;

    public Node(E e, Node<E> n) {
        this.element = e;
        this.next = n;
    }

    public E getElement() {
        return this.element;
    }

    public Node<E> getNext() {
        return this.next;
    }

    public void setNext(Node<E> n) {
        this.next = n;
    }
}

In addition, the SinglyLinkedList class has the following fields:

private Node<E> head = null;

private Node<E> tail = null;

private int size = 0;

The method I am having trouble with is called reverse and its purpose is to reverse the order of a singly linked list in a recursive manner. Here is the code for this method:

public static SinglyLinkedList reverse(SinglyLinkedList l) {
    if (l.size < 2) return l;
    Node first = l.removeFirstNode();
    SinglyLinkedList reversed = reverse(l);
    reversed.addLast(first);
    return reversed;
}

The reverse method uses a non-static method called removeFirstNode whose purpose is to remove the first Node in the singly linked list and return it:

private Node<E> removeFirstNode() {
    if (isEmpty()) return null;
    //Node<E> answer = new Node<>(this.head.getElement(), null);
    Node<E> answer = this.head;
    this.head = this.head.getNext();
    this.size--;
    if (this.size == 0) this.tail = null;
    return answer;
}

The reverse method also uses a non-static method called addLast whose purpose is to add a given Node to the end of a singly linked list:

private void addLast(Node<E> n) {
    if (isEmpty()) this.head = n;
    else this.tail.setNext(n);
    this.tail = n;
    this.size++;
}

The problem is that when I try to run the reverse method on a SinglyLinkedList of size equal to 2 the compiler gets to the line

reversed.addLast(first);

and then inside the addLast method it stops on the line

this.tail = n;

and runs forever without terminating. If size equals 3 or more the compiler gets to the line

reversed.addLast(first);

and stops there without even entering the addLast method. Now if I replace the line

Node<E> answer = this.head;

with the currently commented-out line

Node<E> answer = new Node<>(this.head.getElement(), null);

the reverse method terminates without any issues. Can anybody explain what is going on here?

EDIT: I just realized that the differing behavior for size 3 or more is just an artifact of recursion. The real problem is with the case when size is equal to 2 and the method inexplicably terminates on the line

this.tail = n;

EDIT 2:

Minimal Code:

public class SinglyLinkedList<E>{

private static class Node<E> {
    private E element;
    private Node<E> next;

    public Node(E e, Node<E> n) {
        this.element = e;
        this.next = n;
    }

    public E getElement() {
        return this.element;
    }

    public Node<E> getNext() {
        return this.next;
    }

    public void setNext(Node<E> n) {
        this.next = n;
    }
}

private Node<E> head = null;

private Node<E> tail = null;

private int size = 0;

public SinglyLinkedList() {}

public int size() { return this.size; }

public boolean isEmpty() {
    return this.size == 0;
}

public void addLast(E e) {
    Node<E> newest = new Node<>(e, null);
    if (isEmpty())
        this.head = newest;
    else
        this.tail.setNext(newest);
    this.tail = newest;
    this.size++;
}

@Override
public String toString() {
    String output = "";
    if (this.size > 0) {
        Node<E> current_node = head;
        while (current_node != null) {
            output += current_node.getElement();
            if (current_node != tail) output += ", ";
            else output += "\n";
            current_node = current_node.getNext();
        }
    }
    return output;
}

private void addLast(Node<E> n) {
    if (isEmpty()) this.head = n;
    else this.tail.setNext(n);
    this.tail = n;
    this.size++;
}

private Node<E> removeFirstNode() {
    if (isEmpty()) return null;
    //Node<E> answer = new Node<>(this.head.getElement(), null);
    Node<E> answer = this.head;
    this.head = this.head.getNext();
    this.size--;
    if (this.size == 0) this.tail = null;
    return answer;
}

public static SinglyLinkedList reverse(SinglyLinkedList l) {
    if (l.size < 2) return l;
    Node first = l.removeFirstNode();
    SinglyLinkedList reversed = reverse(l);
    reversed.addLast(first);
    return reversed;
}}

Test Class:

public static void main(String[] args) {
    int n = 4;
    SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
    for (int i = 1; i <= n; i++) list.addLast(i);
    System.out.print(list);
    System.out.print(SinglyLinkedList.reverse(list));
}

Answer 1

The implementation of removeFirstNode() doesn't unlink the next pointer for the node.

In the original linked list, the first node's next point points to the second node, and the second node's next pointer is null.

In the new list, the first node's next pointer will point to the second node, but the second node's next pointer will point to the first node (which used to be the second node).

Something like this (original list):

+---+    +---+
| A |--->| B |--->null
+---+    +---+

When reordered becomes this because A's next pointer still points to B:

+---+    +---+
| B |--->| A |---+
+---+    +---+   |
  ^              |
  |              |
  +--------------+

You could change your removeFirstNode() implementation to be something like this:

    private Node<E> removeFirstNode() {
        if (isEmpty()) return null;
        Node<E> answer = this.head;
        this.head = this.head.getNext();
        answer.next = null; // Set next ptr to null
        this.size--;
        if (this.size == 0) {
            this.tail = null;
        }
        return answer;
    }

The code probably looks like it "stops" because the debugger tries to print out the list using toString(), which I imagine traverses the list and never completes because of the loop.