Apr 22, 2012

Reverse a linked list

One of the frequently asked question in the interviews is to reverse a singly-linked list using iterative and recursive approach.

Iterative Approach
void ireverse()
    {
      Node *current = head;
      Node *prev = NULL;
      Node *next = current->link;

      while(next != NULL)
      {
        current->link = prev;
        prev = current;
        current = next;
        next = next->link;
      }

      current->link = prev;
      head = current;
    }
Recursive Approach
void reverse(Node *current, Node *prev, Node *next)
    {
      if(next == NULL)
      {
        current->link = prev;
        head = current;
        return;
      }
      current->link = prev;
      reverse(next, current, next->link);
    }

1. The complete C++ program can be viewed here
2. Java programmers can find the Java version of the above problem here

No comments :

Post a Comment