Reversing a linked list (Java)
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.