2011-10-13: Reverse Linked List.

One of the most basic problem is to reverse a linked list.
Problem:

Reverse A Linked List.
Example:
          1 -> 2 -> 3 -> 4;
Output:
          4 -> 3 -> 2 -> 1;

	Solution 1	Solution 2	Solution 3
Time	O(2*N)	O(N)	O(N)
Memory	O(2*N)	O(2*N)	O(c = 3)

Solution 1:
Using a recursive function to implement it.
Take 1, then reverse the 2 to 4, add 1 as the end element of the linked list.
PS: I used a while loop to reach the end of linked list, or the node will add as the next element of newNode.

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Node root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(3);
        root.next.next.next = new Node(4);
        Node newRoot = root.reverse();
        while (newRoot != null) {
            System.out.println(newRoot.data);
            newRoot = newRoot.next;
        }
    }
}

class Node {
    public int data;
    public Node right;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        if (node.right == null)
            return node;
        Node newNode = reverse(node.right);
        node.right = null;
        Node next = newNode;
        while (next.next != null)
            next = next.next;
        next.next = node;
        return newNode;
    }
}
Solution 2:
Compare to the reverse function above, I used another node to restore the next node, so I don't need to use the while loop to reach the right-most to insert the current node. Use some extra memory to have less time consuming.

class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        if (node.next == null)
            return node;
        Node secNode = node.next;
        Node newNode = reverse(node.next);
        node.next = null;
        secNode.next = node;
        return newNode;
    }
}

Solution 3:
Using non-recursive way to solve the problem.
class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node reverse() {
        return reverse(this);
    }

    private Node reverse(Node node) {
        Node prev = null;
        Node curr = node;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}