title: compiler won't advance in recursive reversal of singly linked list
body: <p>I have a recursive static method inside a <code>SinglyLinkedList</code> class which runs forever for an undetermined reason. This class is generic and its declaration looks like this:</p>
  
  <pre><code>public class SinglyLinkedList&lt;E&gt;{
  </code></pre>
  
  <p>This class has an inner generic class <code>Node</code> which looks like this:</p>
  
  <pre><code>private static class Node&lt;E&gt; {
      private E element;
      private Node&lt;E&gt; next;
  
      public Node(E e, Node&lt;E&gt; n) {
          this.element = e;
          this.next = n;
      }
  
      public E getElement() {
          return this.element;
      }
  
      public Node&lt;E&gt; getNext() {
          return this.next;
      }
  
      public void setNext(Node&lt;E&gt; n) {
          this.next = n;
      }
  }
  </code></pre>
  
  <p>In addition, the <code>SinglyLinkedList</code> class has the following fields:</p>
  
  <pre><code>private Node&lt;E&gt; head = null;
  
  private Node&lt;E&gt; tail = null;
  
  private int size = 0;
  </code></pre>
  
  <p>The method I am having trouble with is called <code>reverse</code> and its purpose is to reverse the order of a singly linked list in a recursive manner. Here is the code for this method:</p>
  
  <pre><code>public static SinglyLinkedList reverse(SinglyLinkedList l) {
      if (l.size &lt; 2) return l;
      Node first = l.removeFirstNode();
      SinglyLinkedList reversed = reverse(l);
      reversed.addLast(first);
      return reversed;
  }
  </code></pre>
  
  <p>The <code>reverse</code> method uses a non-static method called <code>removeFirstNode</code> whose purpose is to remove the first <code>Node</code> in the singly linked list and return it:</p>
  
  <pre><code>private Node&lt;E&gt; removeFirstNode() {
      if (isEmpty()) return null;
      //Node&lt;E&gt; answer = new Node&lt;&gt;(this.head.getElement(), null);
      Node&lt;E&gt; answer = this.head;
      this.head = this.head.getNext();
      this.size--;
      if (this.size == 0) this.tail = null;
      return answer;
  }
  </code></pre>
  
  <p>The <code>reverse</code> method also uses a non-static method called <code>addLast</code> whose purpose is to add a given <code>Node</code> to the end of a singly linked list:</p>
  
  <pre><code>private void addLast(Node&lt;E&gt; n) {
      if (isEmpty()) this.head = n;
      else this.tail.setNext(n);
      this.tail = n;
      this.size++;
  }
  </code></pre>
  
  <p>The problem is that when I try to run the <code>reverse</code> method on a <code>SinglyLinkedList</code> of <code>size</code> equal to 2 the compiler gets to the line</p>
  
  <pre><code>reversed.addLast(first);
  </code></pre>
  
  <p>and then inside the <code>addLast</code> method it stops on the line</p>
  
  <pre><code>this.tail = n;
  </code></pre>
  
  <p>and runs forever without terminating. If <code>size</code> equals 3 or more the compiler gets to the line</p>
  
  <pre><code>reversed.addLast(first);
  </code></pre>
  
  <p>and stops there without even entering the <code>addLast</code> method. Now if I replace the line</p>
  
  <pre><code>Node&lt;E&gt; answer = this.head;
  </code></pre>
  
  <p>with the currently commented-out line</p>
  
  <pre><code>Node&lt;E&gt; answer = new Node&lt;&gt;(this.head.getElement(), null);
  </code></pre>
  
  <p>the <code>reverse</code> method terminates without any issues. Can anybody explain what is going on here?</p>
  
  <p><strong>EDIT:</strong> I just realized that the differing behavior for <code>size</code> 3 or more is just an artifact of recursion. The real problem is with the case when <code>size</code> is equal to 2 and the method inexplicably terminates on the line</p>
  
  <pre><code>this.tail = n;
  </code></pre>
  
  <p><strong>EDIT 2:</strong></p>
  
  <p>Minimal Code:</p>
  
  <pre><code>public class SinglyLinkedList&lt;E&gt;{
  
  private static class Node&lt;E&gt; {
      private E element;
      private Node&lt;E&gt; next;
  
      public Node(E e, Node&lt;E&gt; n) {
          this.element = e;
          this.next = n;
      }
  
      public E getElement() {
          return this.element;
      }
  
      public Node&lt;E&gt; getNext() {
          return this.next;
      }
  
      public void setNext(Node&lt;E&gt; n) {
          this.next = n;
      }
  }
  
  private Node&lt;E&gt; head = null;
  
  private Node&lt;E&gt; 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&lt;E&gt; newest = new Node&lt;&gt;(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 &gt; 0) {
          Node&lt;E&gt; 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&lt;E&gt; n) {
      if (isEmpty()) this.head = n;
      else this.tail.setNext(n);
      this.tail = n;
      this.size++;
  }
  
  private Node&lt;E&gt; removeFirstNode() {
      if (isEmpty()) return null;
      //Node&lt;E&gt; answer = new Node&lt;&gt;(this.head.getElement(), null);
      Node&lt;E&gt; 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 &lt; 2) return l;
      Node first = l.removeFirstNode();
      SinglyLinkedList reversed = reverse(l);
      reversed.addLast(first);
      return reversed;
  }}
  </code></pre>
  
  <p>Test Class:</p>
  
  <pre><code>public static void main(String[] args) {
      int n = 4;
      SinglyLinkedList&lt;Integer&gt; list = new SinglyLinkedList&lt;&gt;();
      for (int i = 1; i &lt;= n; i++) list.addLast(i);
      System.out.print(list);
      System.out.print(SinglyLinkedList.reverse(list));
  }
  </code></pre>