Difference between pages "3.37" and "3.39"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "<pre> bool compare(struct node* a, struct node* b) { // 1. both empty -> true if (a==NULL && b==NULL) return(true); // 2. both non-empty -> compare them else if (a!...") |
(Created page with "== Iterative version with three variables == <pre> Node* ReverseList( Node * List ) { Node *temp1 = *List; Node * temp2 = NULL; Node * temp3 = NULL; while ( temp...") |
||
Line 1: | Line 1: | ||
+ | == Iterative version with three variables == | ||
<pre> | <pre> | ||
− | + | 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; | ||
+ | } | ||
+ | </pre > | ||
− | + | == Iterative version with one variable == | |
− | |||
− | // | + | <pre> |
− | + | 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); | ||
+ | |||
+ | } | ||
+ | } | ||
+ | </pre> | ||
+ | |||
+ | |||
+ | == Recursive Version == | ||
+ | |||
+ | <pre> | ||
+ | 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; | ||
+ | } | ||
+ | </pre> | ||
+ | --[[User:Max|Max]] 07:36, 16 June 2010 (EDT) | ||
+ | |||
+ | == Recursive Version 2 (Java) == | ||
+ | |||
+ | <pre> | ||
+ | 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; | ||
+ | } | ||
+ | </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> | ||
− | |||
Back to [[Chapter 3]] | Back to [[Chapter 3]] |
Latest revision as of 18:14, 20 September 2020
Contents
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