Last active
October 11, 2016 14:41
-
-
Save mafayaz/d19111ed8f8e423afd75cd93b189455a to your computer and use it in GitHub Desktop.
reversing a linked list in C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
struct Node | |
{ | |
int data; | |
struct Node *next; | |
}; | |
Node* Load(int data[], int size) | |
{ | |
Node *head = NULL; | |
Node *curr = NULL; | |
Node *prev = NULL; | |
for(int i = 0; i < size; i++) | |
{ | |
curr = new Node; | |
curr->data = data[i]; | |
curr->next = NULL; | |
if(prev) prev->next = curr; | |
else head = curr; | |
prev = curr; | |
} | |
return head; | |
} | |
void Print(Node *head) | |
{ | |
bool first = true; | |
cout << "List: ["; | |
while(head) | |
{ | |
if(!first) cout << ", "; | |
first = false; | |
cout << head->data; | |
head = head->next; | |
} | |
cout << "]" << endl; | |
} | |
Node* Reverse(Node *head) | |
{ | |
Node *p0 = NULL; | |
Node *p1 = head; | |
while(p1 != NULL) | |
{ | |
Node* tmp = p1->next; | |
p1->next = p0; | |
p0 = p1; | |
p1 = tmp; | |
} | |
return p0; | |
} | |
Node* ReverseUtil(Node* p0, Node* p1) | |
{ | |
if(p1 == NULL) return p0; | |
Node* t = p1->next; | |
p1->next = p0; | |
p0 = p1; | |
p1 = t; | |
ReverseUtil(p0, p1); | |
} | |
Node* ReverseR(Node *head) | |
{ | |
return ReverseUtil(NULL, head); | |
} | |
int main() | |
{ | |
int data[] = {1,2,3,4,5}; | |
int size = (sizeof(data)/sizeof(*data)); | |
Print(Load(data, size)); | |
Print(Reverse(Load(data, size))); | |
Print(ReverseR(Load(data, size))); | |
return 1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment