Reversing a singly-linked List

Question

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();
            }
            System.out.println("count("+count+") , node value="+temp.getData());
        }
    }
    public static void main(String args[])
    {
        ReverseLL ll=new ReverseLL();
        ll.insert(1);
        ll.insert(2);
        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();
    }
}

Answer 1

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 A<-B<-C

But, we have a couple of loose ends (pun is intended)... we have the start pointer which points at A, and A is pointing at B still, So, we need to remove the now-redundant A->B 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();
    }

Answer 2

"Pointer" golfing?
Continuing rolfl's clean-up; supporting&exploiting chaining:

    public Node setNext(Node n) { Node o=next; next=n; return o; }
…
/** Reverses the list of <code>Node</code>s sporting
 * <code>getNext()</code> and <code>setNext(futureNext)</code> */
public void reverse() {
    for (Node toReverse = start, inTransit = start = null ;
         null != toReverse ; start = inTransit)
        toReverse = (inTransit = toReverse).setNext(start);
    return this;
}

More or less random remarks:
use doc comments
display() is funny - rather override toString()
check corner cases (see, again, rolfl's answer, too); consider using JUnit
consider implementing java.util.List<>/extending java.util.AbstractList<>
rename insert() to append() and add()/insert() at head

        Node(int newData, Node n) { data = newData; next = n; }
…
    /** Inserts <code>newData</code> in front of list. */
    public ReverseLL add(int newData) {
        start = new Node(newData, start);
        return this;
    }
…
public static void main(String args[]) {
    ReverseLL ll = new ReverseLL();
    ll.reverse();
    ll.add(8);
    ll.reverse();
    for (int v = 8 ; 0 < --v ; ) // just learned _ is reserved as of 1.8
        ll.add(v);
    ll.display();
    System.out.println();
    ll.reverse();
    ll.display();
}

Answer 3

You will have to iterate the string twice before taking it into consideration. Loop it once you are done with iteration. I think the while loop works best for this for reversing the print array by proper recursion. Hopefully if the copy array is no longer in use, then it might possibly throw an exception.

Answer 4

emphasized textWithout temp, this is not my code. Please see:https://algorithms.tutorialhorizon.com/reverse-a-linked-list/

//https://algorithms.tutorialhorizon.com/reverse-a-linked-list/

public class ReverseLinkedList {

public static void main (String[] args) throws     java.lang.Exception
{
    LinkedListT a = new LinkedListT();
    a.addAtBegin(5);
    a.addAtBegin(10);
    a.addAtBegin(15);
    a.addAtBegin(20);
    a.addAtBegin(25);
    a.addAtBegin(30);
//  System.out.print("Original Link List 1 : ");
    a.display(a.head);
    a.reverseIterative(a.head);
    LinkedListT b = new LinkedListT();
    b.addAtBegin(31);
    b.addAtBegin(32);
    b.addAtBegin(33);
    b.addAtBegin(34);
    b.addAtBegin(35);
    b.addAtBegin(36);
    System.out.println("");
    System.out.println("___________________");
    System.out.print("Original Link List 2 : ");
    b.display(b.head);
    b.reverseRecursion(b.head,b.head.next,null);
    System.out.println("");
    //b.display(x);
   }
}
class Node{
public int data;
public Node next;
public Node(int data){
    this.data = data;
    this.next = null;
}
}
class LinkedListT{
public Node head;
public LinkedListT(){
    head=null;
}

public void addAtBegin(int data){
    Node n = new Node(data);
    n.next = head;
    head = n;
}
public void reverseIterative(Node head){
    Node currNode = head;
    Node nextNode = null;
    Node prevNode = null;

    while(currNode!=null){
        nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    head = prevNode;
    System.out.println("\n Reverse Through Iteration");
    display(head);
}

public void reverseRecursion(Node ptrOne,Node ptrTwo, Node prevNode){
    if(ptrTwo!=null){
            if(ptrTwo.next!=null){
                Node t1 = ptrTwo;
                Node t2 = ptrTwo.next;
                ptrOne.next = prevNode;
                prevNode = ptrOne;
                reverseRecursion(t1,t2, prevNode);
            }
            else{
                ptrTwo.next = ptrOne;
                ptrOne.next = prevNode;
                System.out.println("\n Reverse Through Recursion");
                display(ptrTwo);
            }
    }
    else if(ptrOne!=null){
        System.out.println("\n Reverse Through Recursion");
        display(ptrOne);
    }
    }

public void display(Node head){
    //
    Node currNode = head;
    while(currNode!=null){
        System.out.print("->" + currNode.data);
        currNode=currNode.next;
    }
    }
  }