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
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = getNewNode(data);
}
}

// create a list
node *createList() {
}

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

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