Skip to content

Instantly share code, notes, and snippets.

@mafayaz
Last active October 11, 2016 14:41
Show Gist options
  • Save mafayaz/d19111ed8f8e423afd75cd93b189455a to your computer and use it in GitHub Desktop.
Save mafayaz/d19111ed8f8e423afd75cd93b189455a to your computer and use it in GitHub Desktop.
reversing a linked list in C++
#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