## Thursday, October 13, 2011

One of the most basic problem is to reverse a linked list.
Problem:
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;
}
}