CareerCup

the code above is wrong.
a-->b-->c-->d

after the first iteration you'll get

a<-->b c-->d

The following version should work:

struct node *reverse(struct node *head)
{
struct node *temp1;
struct node *temp2;
/*if head is null, return */
if (!head) return NULL;

temp1 = head->next;
head->next = NULL;

while (temp1 != NULL) {
temp2 = temp1->next;
temp1->next = head;
head = temp1;
temp1 = temp2;
}
}

void reverseList(node* a)
{
node* curr = head;
node* result = NULL;
node* next;

while(curr != NULL)
{
next = curr->next; // save the curr->next into next

curr->next = result; // copy onto the result node
result = curr;

curr = next;
}

head = result;
}

void reverse(LinkedList& list)
{
node& newHead=list.head;
node& iter=list.head.next;
node& remain;

while(iter.next!=NULL)
{
remain=iter.next;
iter.next=newHead;
newHead=iter;
iter=remain;
}

iter.next=newHead;
newHead=iter;

list.tail=list.head;
list.tail=NULL;
list.head=newHead;
}

Basically, the algorithm is as follows...

5 4 3 2 1
---------
4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5

oops. 2nd to last line should be list.tail.next=NULL

My versions:

Recursive
_________

node * ReverseLinkedList( node * head){

node * currentNode = head;
node * tempNode;

if(currentNode->next == NULL){

return currentNode;

}
else{

tempNode = ReverseLinkedList(currentNode->next);
currentNode->next->next = currentNode;
currentNode->next = NULL;
return tempNode;

}
}

Non-recursive
------------

node * ReverseLinkedList(node * head){

node * currentNode = head;
node * previousNode = NULL;
node * tempNode;

while(currentNode != NULL){
tempNode = currentNode->next;
currentNode->next = previousNode;
previousNode = currentNode;
currentNode = tempNode;
}

return previousNode;

}

My versions:

Recursive
_________

node * ReverseLinkedList( node * head){

node * currentNode = head;
node * tempNode;

if(currentNode->next == NULL){

return currentNode;

}
else{

tempNode = ReverseLinkedList(currentNode->next);
currentNode->next->next = currentNode;
currentNode->next = NULL;
return tempNode;

}
}

Non-recursive
------------

node * ReverseLinkedList(node * head){

node * currentNode = head;
node * previousNode = NULL;
node * tempNode;

while(currentNode != NULL){
tempNode = currentNode->next;
currentNode->next = previousNode;
previousNode = currentNode;
currentNode = tempNode;
}

return previousNode;

}

Another condition in the beginning is:
if(currentNode == NULL) return NULL;

Here is a neat clean recursive code I have come up with, using a wrapper function
mynode * reverseList(mynode *head){
return recursive_reverse(head,NULL);
}

mynode* recursive_reverse(mynode *head, mynode *prev) {
mynode *temp;

if (NULL==head)
return NULL;
temp=head->next;
head->next=prev;
if (NULL==temp)
return head;
return recursive_reverse(temp,head);
}

Recursive:

Node* Reverse(Node* current, Node* prev){
____if(current)
________Node* head = Reverse( current->next, current);
____else
________return prev;

____current->next = prev;
}

Iterative:

Node* Reverse( Node* head){
____Node* prev=NULL, current=head, after=head->next;
____while(current){
________current->next = prev;
________prev=current;
________current=after;
________after=current->next;
____}
____return prev;
}

On the last line of the recursive solution put:

return head;

struct node *reverse(struct node *head)
{
struct node *temp;
/*if head is null, return */
if (!head) return NULL;

while (head->next != NULL) {
temp = head->next;
temp->next = head;
head = temp;
}
}

just use a stack to push all elements in
and recreate the link list with pop operation

recursion version and tail-recursion version C/C++

struct Node * reverseList(struct Node * head) {
struct Node * curNode = head ;
struct Node * nextNode = NULL ;
if ((curNode==NULL)||(curNode->next==NULL)){
return head ;
}
nextNode = reverseList(curNode->next) ;
curNode->next->next = curNode ;
curNode->next = NULL ;
return nextNode;
}

struct Node * reverseListTailRecursion(struct Node * remaining, struct Node * newList) {
struct Node * curNode = remaining ;
struct Node * nextNode = NULL ;
if (curNode->next==NULL){
curNode->next = newList ;
return curNode ;
} else {
nextNode = curNode->next ;
curNode->next = newList ;
return reverseListTailRecursion(nextNode, curNode) ;
}
}

struct Node * reverseListTail(struct Node * head) {
struct Node * curNode = head ;
struct Node * nextNode = NULL ;
if ((curNode==NULL)||(curNode->next==NULL)){
return head ;
} else {
nextNode = curNode->next ;
curNode->next = NULL ;
return reverseListTailRecursion(nextNode, curNode) ;
}
}

this is a recursive approach.

public static Nodes rev(Nodes head, Nodes previous)
    {
        Nodes temp;
        if(head.next==null)
        {
            head.next=previous;
            return head;
        }
        else
        {
            temp=rev(head.next,head);
            head.next=previous;
            return temp;
        }
      
              
    }

Here is the non-recursive:

public static Nodes brev(Nodes head)
    {
        Nodes temp;
        Nodes previous=null;
        while(head!=null)
        {
            temp=head.next;
            head.next=previous;
            previous=head;
            head=temp;
        }
        return previous;
              
    }

Helps to know both in the interview, depending on what is crucial to the interview.