Reversing a singly linked list Java

Question

This is my code for reversing a linked list. I take in the root Node in the method and I use three pointer Nodes to act as previous, current, and next Nodes.

My code reverses the list itself, but I want to reassign the 'root' Node to be at the end of the list since it is going in the opposite direction so I assigned it to the current Node.

But I noticed that the 'current' Node changes its value back to the 1 (the value of the original Root Node) as soon as it exits the while loop. Is there a reason why it does this and how would I remedy it?

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Node root = new Node();

    root.data = 1;
    root.next.data = 2;
    root.next.next.data = 3;
    root.next.next.next.data = 4;
    root.next.next.next.next.data = 5;

    Node tmp = reverse(root);

    System.out.println(tmp.data);
}

public static Node reverse(Node root)
{
    if (root == null || root.next == null)
        return root;

    Node previous = null;
    Node current = root;
    Node next = root.next;

    while (next != null)
    {
        current.next = previous;
        previous = current;
        current = next;
    //  System.out.println(current.data);
        next = current.next;
    }

    root = current;

    return root;
}

Davis Davis · Accepted Answer · 2014-10-23T02:27:59

You may try this, you give the wrong value of root at the end:

public static Node reverse(Node root){
    if(!root) return root;
    Node previous = null;
    Node current = root;
    while(current){
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    root = previous;
    return root;
}

Reversing a singly linked list Java

1 Answers