Linked List

Problem 
Reverse a linked list in an efficient manner.

Solution 
This is one of the most frequently asked algorithm in interviews. The algorithm illustrates how smart pointer movements can make a task very efficient. Logic is simple. It involves iterating over the list with one pointer and another pointer points to a head of a reversed list (which starts with NULL). Remove nodes from original list and add them to the head of the reversed list. We need not allocate any extra memory to solve the problem. It’s just some pointer movements which does the magic. See the implementation below to get more clarity on the approach.

#include<iostream>
using namespace std;

// list node structure
typedef struct list_node {
   int data;
   struct list_node *next;
}node;

// create new node
node *getNewNode(int data) {
   node *new_node = new node;
   new_node->data = data;
   new_node->next = NULL;
   return new_node;
}


// append a node to the list
void addNodeToList(node **head, int data) {
   if (*head == NULL)
      *head = getNewNode(data);
   else {
      node *ptr = *head;
      while (ptr->next != NULL)
         ptr = ptr->next;
      ptr->next = getNewNode(data);
   }
}

// create a list
node *createList() {
   node *head = NULL;
   addNodeToList(&head,12);
   addNodeToList(&head,7);
   addNodeToList(&head,11);
   addNodeToList(&head,19);
   addNodeToList(&head,9);
   return head;
}

// traverse the list
void traverseList(node *head) {
   node *ptr = head;
   while (ptr != NULL) {
      cout<<ptr->data<<" ";
      ptr = ptr->next;
   }
}

// reverse the list
node *reverseList(node *head) {
   node *start = head;
   node *ptr = head;
   node *temp = NULL;
   while (start != NULL) {
      ptr = start->next;
      start->next = temp;
      temp = start;
      start = ptr;
   }
   head = temp;
   return head;
}

// main
int main() {
   node *head = createList();
   cout<<"\nOriginal List :-\n";
   traverseList(head);
   head = reverseList(head);
   cout<<"\nReversed List :-\n";
   traverseList(head);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list
About    Contact    Sitemap    Terms    Privacy