You are asked to write a function Node Reverse(Node head) which has a pointer to the head element of the linked list as a parameter and need to reverse the list and return pointer to the new head element:
This is classical interview question which surprisingly is unexpected by many candidates . This is also a basis problem and understanding solution will help you to solve number of linked list problems.
The key to understand in this problem is that the only thing needed just changing direction of a pointer as in opposing to an array data structure we don’t need to worry about sequential location of elements in memory.
Possible Solution:
public Node Reverse(Node head)
{
Node next;
Node current;
current = head;
Node Result = null;
while (current != null)
{
next = current.next;
current.next = result;
result = current;
current = next;
}
return (result);
}
static Node ListReverse(Node N){
Node N_ = new Node();
N_ = RReverse(N, N.Next);
N.Next = null;
return N_;
}
static Node RReverse(Node n, Node n_){
if(n_ == null)return n;
Node n__ = n_.Next;
n_.Next = n;
return RReverse(n_, n__);
}