TADM2E 3.23

From Algorithm Wiki
Jump to: navigation, search

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;
}