CareerCup

There are 2 ways: recursion or iterative. I like iterative more (is O(1) space) but it's a little more complicated.

C#:
struct Node {
 int val;
 Node next; 
}

Node reverse(Node head) {
 if (head == null || head.next == null) return head;

 Node t = head, p = null;
 while (t != null && t.next != null) {
  Node n = t.next;
  Node nn = n.next;
  // change pointers
  t.next = p;
  n.next = t;
  p = n;
  t = nn;
 }

 if (t != null)
  t.next = p;

 return (t != null) ? t : p;

}

1)push each node of L.L on to the stack and ...

2)Pop the stack and make a L.L till stack becomes empty..

public class LinkedList {

protected Node head;

protected LinkedList()
{
head = null;
}

public void reverseLinkedList()
{
Node n = reverseList(head.next);
n.next = null;
}

private Node reverseList(Node node)
{
if(node.next!=null)
{
Node prev = node;
node = reverseList(node.next);
node.next = prev;
return prev;
}
else
{
head.next = node;
return node;
}

/*Stack<Node> nodes = new Stack<Node>();

while(node.next!=null)
{
nodes.push(node);
node = node.next;
}

nodes.push(node);
System.out.println("Pushed: " + node.data);

//head = null;
head = null;
head = new Node();
head.next = nodes.pop();
Node n = head.next;
Node n1 = null;

try{

while(nodes.peek()!= null)
{
Node na = nodes.pop();
n.next = na;
System.out.println(na.data);

}
}
catch(Exception ex)
{

}

return head;*/
}
}

//The Commented Code has solution using Stack. But it throws Stack Exception. I //tried the recursive approach instead. Stack works fine too, just need to check the
//StackEmpty Exception.

struct List
{
int data;
List * link;
};

List * reverse(List * L)
{
List *node=NULL:
if(L -> link == NULL)
{
return node = L;
}
node=reverse(L -> link);
L -> link ->link = L ->link;
L -> link =NULL;
return node;
}

in above code replace L -> link -> link = L ->link;
by L -> link ->link = L;

//'start' is the first node of the linked list
reverse (struct node *start) {
struct node *p = start;
struct node *q = start;
struct node *r = NULL;
while (q) {
q = p->next;
p->next = r;
r = p;
p = q;
}
start = r;
}

Here is java solution of the problem:

/**
*
* @author Brijpal Singh
* @date Feb 7, 2011
*/
public class Main {

public static void main(String[] args) {
final Node head = new Node(new Integer(1));
Node node = append(head, 2);
node = append(node, 3);
node = append(node, 4);
node = append(node, 5);
node = append(node, 6);
node = append(node, 7);
System.out.println(head);
System.out.println(revisedReverse(head));
}

private static Node append(Node node, int value) {
Node node2 = new Node(new Integer(value));
node.next = node2;
return node2;
}

/**
* Main class to reverse the linked list
*
* @param head
* @return
*/
private static Node revisedReverse(Node head){
if(head == null || head.next == null){
return head;
}

Node pre = head;
Node curr = pre.next;
Node next = curr.next;
head.next = null;

while(next.next !=null){
curr.next=pre;

pre = curr;
curr = next;
next = next.next;
}
curr.next=pre;
next.next=curr;

return next;
}

private static class Node{
private Object value;
private Node next;
/**
* @param value
*/
public Node(Object value) {
this.value = value;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return value.toString()+"-->"+next;
}
}
}