Reversing a singly-linked List

Is this the best way to reverse a singly-linked list? Can it be done with two, or fewer pointers? Any other comments?

```
public class ReverseLL {
Node start;
ReverseLL()
{
start=null;
}
class Node
{
Node next;
int data;

Node(int newData)
{
next=null;
data=newData;
}
public void setData(int newData)
{
data=newData;
}
public int getData()
{
return data;
}
public void setNext(Node n)
{
next=n;
}
public Node getNext()
{
return next;
}

}
public void insert(int newData)
{
Node p=new Node(newData);
if(start==null)
{
start=p;
}
else
{
Node temp=start;
while(temp.getNext()!=null)
{
temp=temp.getNext();
}
temp.setNext(p);
}
}

public void reverse()
{
Node temp=start;
Node previous=null;
Node previous1=null;
while(temp.getNext()!=null)
{
if(temp==start)
{
previous=temp;
temp=temp.getNext();
previous.setNext(null);
}
else
{
previous1=temp;
temp=temp.getNext();
previous1.setNext(previous);
previous=previous1;
}
}
temp.setNext(previous);
start=temp;
}
public void display() {
int count = 0;

if(start == null) {
System.out.println("\n List is empty !!");
} else {
Node temp = start;

while(temp.getNext() != null) {
System.out.println("count("+count+") , node value="+temp.getData());
count++;
temp = temp.getNext();

This is a nice, clean implementation of a Linked list... Generally a good job.

You have a bug in your reverse method, a NullPointerException when the list is empty. There is an easy fix, but you should be aware.

I also had a look at your reverse method. I cannot see a way to do it with fewer than 3 variables, while still keeping the logic readable. I am not particularly fond of your implementation... The distinct if/else condition makes the internal logic cumbersome. It makes things easier if you consider the process to be closer to a swap... we want to swap the direction of the pointer between nodes.

So, the logic is, for three nodes A->B->C, we want to make B point to A, but, we have to remember that C comes after B before we reverse the pointer. Then we have to make C point to B, becoming AB pointer, and also move start to point at C..... All so complicated, but it boils down to a simple loop:

public void reverse() {
        if (start == null) {
            return;
        }
        Node current = start;
        Node after = start.next;
        while (after != null) {
            Node tmp = after.next; // preserve what will come later.
            after.next = current;  // reverse the pointer
            current = after;       // advance the cursor
            after = tmp;           // the node after is the one preserved earlier.
        }
        start.next = null;         // null-out next on what was the start element 
        start = current;           // move the start to what was the end.
    }

This, to me, is much more readable than the conditional logic you had. It does use three pointers in addition to the start.

If you want to, you can probably find a way to do it with one less pointer, but that is by hacking the start pointer and using it as a tracker in the loop (probably instead of current, but the readability, and simplicity will suffer if you do that.

Note also that Java coding convention puts the { open brace at the end of the line containing the conditional block.

Finally, at the risk of adding a little complexity to your code, most general-purpose Linked Lists in 'real' applications have an O (1) mechanism for getting the List size. If you have a custom purpose for the list where the size is not important, you can skip that, but, you should otherwise consider adding a size field so you can avoid doing a full iteration to get the size.

Another Finally, The Java Iterator concept is a very common idiom. It is surprisingly complicated though to get your implementation to match the specification. I strongly recommend that you take it upon yourself to make your List iterable, and to make sure your Iterator implementation conforms to the specification (especially the conditions under which the iterator throws exceptions).

I also extended your main method to do a few more tests than you have:

public static void main(String args[]) {
        ReverseLL ll=new ReverseLL();
        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(1);
        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(2);

        ll.reverse();
        ll.display();
        System.out.println();

        ll.reverse();
        ll.display();
        System.out.println();

        ll.insert(3);
        ll.insert(4);
        ll.insert(5);
        ll.insert(6);
        ll.insert(7);
        ll.insert(8);
        ll.display();
        System.out.println();

        ll.reverse();
        ll.display();
        System.out.println();
    }

StackExchange Code Review Q#39254, answer score: 8