Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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();
    }
}
share|improve this question
    
I have used temp, previous and previous1 –  happs Jan 15 '14 at 0:48
    
Why? Is this some sort of challenge that you have to restrict it this way? –  rolfl Jan 15 '14 at 0:49
    
took a lot of liberty editing and indenting your code. If you have an issue with it, feel free to roll it back. I won't take offense. –  rolfl Jan 15 '14 at 0:56
    
you might understand the dynamics why three pointers are necessary. It seems to be not possible in an iterative approach to do it in less pointers. I tried to explain the same here techieme.in/reversing-a-singly-linked-list –  dharam Apr 19 at 15:41

1 Answer 1

up vote 3 down vote accepted

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, this 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 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 compliated, 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();
    }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.