Reversing a linked list (Java) Triggered by an interview question (I didn't answer during the interview) I wrote a Java program to reverse a linked list. I went with a loop-based approach instead of recursion. I would like to know the following:


Is the reverse() method efficient as it is, or can it be improved?
Are the inline comments inside the reverse() method clear or are they confusing and/or superfluous?


The following is the code for the entire LinkedList class I wrote, containing a public reverse() method:

public class LinkedList&lt;T&gt; {
    /**
     * A Node represents a single item inside the linked list. Each node contains
     * the value of the item and a pointer to the next node.
     */
    class Node {
        T value;
        Node next;
    }

    /**
     * The 'head' is the beginning of the linked list.
     */
    Node head;

    /**
     * Add an item to the end of the linked list.
     * 
     * @param value - The value of the item to be added
     */
    public void add(T value) {
        // Create the new node to be added
        Node newNode = new Node();
        newNode.value = value;

        // If list is empty, add it at the head
        if (head == null) {
            head = newNode;
            return;
        }

        // If the list is not empty, find the end of the list and add it there
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    /**
     * Perform an in-place reversal of the elements in the linked list.
     * 
     * After this method is called, the order of the elements in the linked list
     * will be reversed.
     */
    public void reverse() {
        Node current = head;        // Start at the beginning
        Node previous = null;       // In each iteration, points to the current node's previous node
        Node next;                  // In each iteration, we use this to backup the current node's next node
        while (current != null) {
            next = current.next;        // Backup current node's next node
            current.next = previous;    // Point current node backwards - to the previous node
            previous = current;         // Set new previous to current node, for next iteration
            head = current;             // Point head to current, so by end of loop, it will point to the original tail
            current = next;             // Point current to the original next node, for next iteration
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("");
        Node current = head;
        while (current != null) {
            sb.append(current.value + " ");
            current = current.next;
        }
        return sb.toString();
    }
}


The following is the code I used to test the above method, just in case it is required:

public class LinkedListReversal {
    public static void main(String[] args) {
        LinkedList&lt;Integer&gt; list = new LinkedList&lt;&gt;();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.println(list);

        list.reverse();

        System.out.println(list);
    }
}
Questions


  Is the reverse() method efficient as it is, or can it be improved?


You cannot reverse a standard linked list without touching all its nodes, which has a lower-bound asymptotic complexity of o(N) operations.  Your reverse() method has O(N) complexity and uses O(1) extra space, so you cannot improve its asymptotic complexity in either of those dimensions.  Note that the usual recursive solution consumes o(N) overhead, all on the stack, so an iterative implementation is clearly a superior choice.

You could, however, make it slightly more efficient by updating head just once, at the end, instead of at every iteration.  In particular, instead of head = current; inside the loop, you could use head = previous; immediately after the loop.  No other changes would be required.

Consider, however, that if speed of the reverse() method were of paramount importance, such that it was reasonable to sacrifice a bit of list-traversal performance, then you could create a List class for which reverse() is O(1).  I would do that with an internal circular, doubly-linked list of Nodes, with node traversal performed via a Node method that relies on an instance variable of the host List to determine which direction to consider as forward.  With such a structure, (logically) reversing the list would be achieved simply by changing the value of the single variable that controls list direction.  Example:

int direction = 0;

class Node {
    T value;
    Node[] links = new Node[2];
    public Node next() {
        assert ((direction &gt;= 0) &amp;&amp; (direction &lt; links.length));
        return links[direction];
    }
}

public void reverse() {
    direction = 1 - direction;
}



  Are the inline comments inside the reverse() method clear or are they confusing and/or superfluous?


They are both clear and largely superfluous.  You've chosen reasonably good names for your variables, so the meaning of the code is fairly well readable from the code itself.  More generally, I rarely think it appropriate to comment every single one of a series of simple statements.  It is more effective to document at a somewhat higher level: if each statement reads well in and of itself then document the purpose of groups of lines.

Also, I prefer trailing comments to be very short.  If you have something longer to say then put it on its own line or lines.

Additional comments

Clearly your LinkedList class is constructed for the express purpose of demonstrating reverse(), as it is missing methods that one would expect a general-purpose list class to provide.  That might or might not be an issue if you were to present such an answer in an interview.  Note that you could provide a full-featured implementation of java.util.List by extending AbstractSequentialList and implementing its listIterator() method.

On general principles, the inner Node class should have a constructor with which its value field and maybe its next field can be initialized.  It may be appropriate to make the value final, too, as @forsvarir also suggested -- this is possible only if you provide a constructor.