Difference between revisions of "TADM2E 3.23"

From Algorithm Wiki
Jump to: navigation, search
 
(4 intermediate revisions by one other user not shown)
Line 69: Line 69:
  
 
<pre>
 
<pre>
public Node reverse(Node previousNode){
+
void reverseList(){
 +
head.reverse(null);
 +
Node temp=head;
 +
head=tail;
 +
tail=temp;
 +
}
 +
 
 +
public void reverse(Node previousNode){
 
if(next!=null)
 
if(next!=null)
 
next.reverse(this);
 
next.reverse(this);
 
next=previousNode;
 
next=previousNode;
return this;
+
}
 +
</pre>
 +
 
 +
== Recursive Version 3 (C++) ==
 +
 
 +
<pre>
 +
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;
 +
  }
 
}
 
}
 
</pre>
 
</pre>

Latest revision as of 02:24, 13 July 2019

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