# Reverse a single linked list

In this article, we are going to see how to reverse a single linked list? This problem has come to coding round of Amazon, Microsoft.
Submitted by Radib Kar, on December 02, 2018

Problem statement: Given a linked list reverse it without using any additional space (In O(1) space complexity).

Solution:

Reversing a single linked list is about reversing the linking direction. We can solve the above problem by following steps:

Firstly, we build the linked list by inserting each node at the beginning. For detailed analysis of how to build a linked list using insertion at beginning, kindly go through this full article: Single linked list insertion

2. Function to reverse the link list

As told previously, the basic idea to reverse a linked list is to reverse the direction of linking. This concept can be implemented without using any additional space. We need three pointers *prev, *cur, *next to implement the function. These variables are named accordingly to indicate their serving part in the function.

*prev - to store the previous node which will become ultimately the next node after reversal for current node

*cur - to store the current node

*next - to store the next node which will become current node in the next iteration.

Initialize *prev & *next to NULL, *cur to head

```while(cur!=NULL)
Set *nextto cur->next
Set cur->nextto *prev
Set *prev to *cur
Set *cur to *next
End While loop
```

3. Print the reversed linked list

Example:

```Let the linked list be 1->2->3->4->5->NULL
(for simplicity in understanding representing
pointer to node by node value)
Initialize:
cur =1, prev=NULL, next=NULL

in iteration 1:
next=2
cur->next=NULL
prev=1
cur=2
thus reversed part: 1->NULL

in iteration 2:
next=3
cur->next=1
prev=2
cur=3
thus reversed part: 2->1->NULL

in iteration 3:
next=4
cur->next=2
prev=3
cur=4
thus reversed part: 3->2->1->NULL

in iteration 4:
next=5
cur->next=3
prev=4
cur=5
thus reversed part: 4->3->2->1->NULL

in iteration 5:
next=NULL
cur->next=4
prev=5
cur=NULL
thus reversed part: 5->4->3->2->1->NULL
iteration ends at cur is NULL
```

## C++ program to reverse a single linked list

```#include<bits/stdc++.h>

using namespace std;

class node{
public:
int data; // data field
node *next;
};

while(cur!=NULL){//loop till the end of linked list
next=cur->next;//next = cur->next to store the rest of the list;
cur->next=prev;//change the direction of linked list
prev=cur; //update prev
cur=next; //update cur
}

}

int count=0; // to count total no of nodes
printf("\ntraversing the list\n");
while(current!=NULL){ //traverse until current node isn't NULL
count++; //increase node count
printf("%d ",current->data);
current=current->next; // go to next node
}
printf("\ntotal no of nodes : %d\n",count);
}

node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}

int main(){
printf("creating the linked list by inserting new nodes at the begining\n");
printf("enter 0 to stop building the list, else enter any integer\n");
int k,count=1,x;

node* curr;

scanf("%d",&k);
node* head=creatnode(k); //buliding list, first node
scanf("%d",&k);

//inserting at begining////
while(k){
curr=creatnode(k);
curr->next=head;   //inserting each new node at the begining
scanf("%d",&k);
}

cout<<"reversing the list............"<<endl;

return 0;
}
```

Output

```creating the linked list by inserting new nodes at the begining
enter 0 to stop building the list, else enter any integer
6
7
8
9
4
3
3
1
0

traversing the list
1 3 3 4 9 8 7 6
total no of nodes : 8
reversing the list............

traversing the list
6 7 8 9 4 3 3 1
total no of nodes : 8
```