Thursday, May 27, 2010

How to reverse a linked list

How to reverse a linked list


//compile with g++ 
#include <iostream>
using namespace std;

struct Node 
{
  Node(Node* _next, int _value) 
  { 
    next = _next; 
    value = _value; 
  }

  ~Node()
  { if(next != NULL) delete next; }

  Node* next;
  int value;
};

Node* reverse(Node* head)
{
  Node* new_head = NULL; 
  Node* current  = NULL; 
  
  while(head != NULL)
    {
      current = head;
      head = current->next;
      current->next = new_head;
      new_head = current;
    }

  return new_head;
}

//test
void print(Node* current)
{
  while(current != NULL)
    {
      cout << current->value << " ";
      current = current->next;
    }
  cout << endl;
}

int main()
{
  Node* head = NULL;

  for(int i = 0; i < 10; i++)
    head = new Node(head, i);

  print(head);
  head = reverse(head);
  print(head);

  delete head;
}

No comments:

Post a Comment