3.39

Iterative version with three variables

Node* ReverseList( Node * List )      
{
  Node *temp1 = *List;
  Node * temp2 = NULL;
  Node * temp3 = NULL;
  while ( temp1 )
  {
        *List = temp1; //set the head to last node           
        temp2= temp1->pNext; // save the next ptr in temp2
        temp1->pNext = temp3; // change next to privous
        temp3 = temp1;
        temp1 = temp2;
   }
   return *List;
}

Iterative version with one variable

 
Node* reverse (node* head)
{
    node *temp=NULL;
    while(true)
    {
        if(head->next==NULL)
        {
            head->next=temp;
            break;
        }
        // Swap(head->next, temp)
        head->next = (node *)((unsigned long) head->next ^(unsigned long) temp);
        temp = (node *)((unsigned long) head->next ^(unsigned long) temp);
        head->next =(node *) ((unsigned long) head->next ^ (unsigned long)temp);
        
        // Swap(head, temp)
        head = (node *)((unsigned long) head ^(unsigned long) temp);
        temp =(node *) ((unsigned long) head ^(unsigned long) temp);
        head =(node *) ((unsigned long) head ^ (unsigned long)temp);
        
    }
}

Recursive Version

Node* Reverse(Node*head)
{
   Node* temp=NULL;
   if(head==NULL)
   {
       return NULL;
   }
   if(head->next==NULL)
       return head;
   temp=Reverse(head->next);
   head->next->next=head;
   head->next=NULL;
   return temp;
}

--Max 07:36, 16 June 2010 (EDT)

Recursive Version 2 (Java)

void reverseList(){
	head.reverse(null);
	Node temp=head;
	head=tail;
	tail=temp;
}

public void reverse(Node previousNode){
	if(next!=null)
		next.reverse(this);
	next=previousNode;
}

Recursive Version 3 (C++)

struct node{
   int data;
   node* next;
};

node* new_head; // store the new head after calling reverse_sll function

void reverse_sll(node* current_node, node* prev_node=NULL){
   if(current_node==NULL)
      new_head = prev_node;
   else{
      reverse_sll(current_node->next, current_node);
      current_node->next=prev_node;
   }
}

Back to Chapter 3