The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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