# Reverse a Linked List

Reverse a Linked List” is one of the favourite technical interview problem based on Linked List. Here, we are given a linked list and our task is to reverse the given list.

NOTE: We need to reverse the order of the nodes, not reverse the data value of nodes.

The steps required to reverse a linked list are as follows:

1. Initialize resultant list as NULL.
2. Traverse the complete list. While traversing the linked list, for every node encountered, remove that node, and add that node to the beginning of resultant list.
3. At last, head of the resultant linked list will become the head of the original Linked List.

#### C++ Program to reverse a linked list is as follows:

```/* C++ Program to Reverse a Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Strcuture of the Node of Linked List */
typedef struct node
{
int data;
struct node *next;
}Node;

/* Function to Insert Nodes in the Linked List */
void insert_end(Node **head, int ele)
{
/* Creating a new node */
Node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;

/* Check whether the linked list is empty or not */

/* If Linked List is Empty */
if(*head == NULL)
{
*head = new_node;
return;
}

/*
If Linked List is not empty, then traverse the complete linked list and
pointer of last node of the linked list will point to the new node of
the Linked List.
*/
Node *temp = NULL;
temp = (*head);
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}

/* Function to Reverse a Linked List */
Node *reverse(Node *head)
{
Node *res = NULL;
Node *temp = head;

/*
Traverse the complete Linked List and remove nodes one-by-one from the linked List
and add them at the beginning of the resultant linked list.
*/
while(temp!=NULL)
{
Node *p = temp;
temp = temp->next;
p->next = NULL;
p->next = res;
res = p;
}

/* Head of resultant Linked List will become head of original linked list */
head = res;
return head;
}

/* Function to print the Linked List */
void print(Node *head)
{
Node *temp = head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
Node *head;
head = NULL;
/* Insert Some Nodes in the Linked List */
insert_end(&head,45);
insert_end(&head,78);
insert_end(&head,89);
insert_end(&head,93);
insert_end(&head,99);
cout<<"Linked List Before Reversing:\n";
print(head);
/* Reverse a Linked List */
head = reverse(head);
cout<<"\nLinked List after Reversing:\n";
print(head);
}
```
```OUTPUT:
Linked List before Reversing:
45 78 89 93 99
Linked List after Reversing:
99 93 89 78 45```

Related Posts: