# Reverse a linked list using 2 pointers technique using XOR operator

You must have come across **reversing a linked list** using **3 pointers technique** which is the most common approach to do it. But do you know how to reverse a linked list with **just 2 pointers**? This article will teach you just that! Let's dive into it.

# Introduction

Let us consider the following input :

(**^** represents the **head pointer** to the list)

**Input :**

1 -> 2 -> 3 -> 4 -> 5

^

Our objective is to reverse the linked list by reversing its links

**Expected Output :**

1 <- 2 <- 3 <- 4 <- 5

..............................^

Before we dive into 2 pointer technique, let us take a look at the 3 pointer technique to reverse a linked list.

## Implementation in C++

```
//Reverse a linked list using 3 pointers
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node *nptr;
};
struct node *hptr=NULL;
void insertNode(int pos, int x)
{
struct node *temp=new node;
if(temp==NULL)
cout<<"Insert not possible\n";
temp->data=x;
if(pos==1)
{
temp->nptr=hptr;
hptr=temp;
}
else
{
int i=1;
struct node* thptr=hptr;
while(i<pos-1)
{
thptr=thptr->nptr;
i++;
}
temp->nptr=thptr->nptr;
thptr->nptr=temp;
}
}
void reverseList()
{
struct node* current=hptr;
struct node* next;
struct node* prev=NULL;
while(current!=NULL)
{
next=current->nptr; //line 1
current->nptr=prev; //line 2
prev=current; //line 3
current=next; //line 4
}
hptr=prev;
}
void print()
{
struct node* temp=hptr;
while(temp!=NULL)
{
cout<<temp->data<<"\n";
temp=temp->nptr;
}
}
int main()
{
insertNode(1,10);
insertNode(2,20);
insertNode(3,30);
insertNode(4,40);
insertNode(5,50);
reverseList();
print();
return 0;
}
```

**Output :**

```
50
40
30
20
10
```

## What is happening in the code? Step by step explanation

Let us take a look at the **reverseList()** function.

We have 3 pointers : **next** pointer, **current** pointer and **prev** pointer. Our objective is to iterate over every node and make it point to the previous node (reverse every node's link). Sounds simple right ?

Let's take the same example of the linked list

1 -> 2 -> 3 -> 4 -> 5 -> NULL

We need to reverse the link of every node, that is, make **1** to point to **NULL**, **2** to point to **1**, **3** to point to **2**, **4** to point to **3**, and **5** to point to **4** and at last make **head pointer** point to the node containing value **5**.

NULL <- 1 <- 2 <- 3 <- 4 <- 5

What should we do to get achieve this link reversal?

We need to make the current node point to the previous node (link reversal). Let's try that.

Also remember that **current** is pointing to the 1st node (current = hptr) and **prev** is pointing to **NULL**.

At first my current is pointing to node with value 1

1 -> 2 -> 3 -> 4 -> 5

^

If I make `current->nptr = prev`

, that would result in :

1 -> NULL, 2 -> 3 -> 4 -> 5

**NOTE :** The link between node 1 and node 2 is lost when node 1 points to NULL. A node cannot point to 2 different locations

Now, the **head pointer** is pointing to node containing **1** and the rest of the list is lost (we do not have any reference to the list and hence cannot access it and is lost!)

We don't want this to happen . So we bring in another pointer **next** to have a reference to the list.

Before we make `current->nptr = prev`

(reversal of link), we first update the **next pointer** as `next=current->nptr;`

( * is **prev** , ^ is **current** , and $ is **next**)

1 -> 2 -> 3 -> 4 -> 5

^.....$

Now let us make:

```
current->nptr = prev
```

We now have reference to the rest of the list too!

We have successfully reversed the link of the 1st node. To reverse the link of the next node, our **prev** should become the 1st node and our **current** should become the 2nd node.

So, we need to update **prev** and **current**.

```
prev = current;
current = next;
```

End of Iteration 1 :

1 -> NULL , 2 -> 3 -> 4 -> 5

*..................^$

Keep repeating this procedure until the last node.

End of Iteration 2 :

NULL <- 1 <- 2 , 3 -> 4 -> 5

.......................*..^$

End of Iteration 3 :

NULL <- 1 <- 2 <- 3 , 4 -> 5

..............................*...^$

End of Iteration 4 :

NULL <- 1 <- 2 <- 3 <- 4 , 5

.....................................*...^$

End of Iteration 5 :

NULL <- 1 <- 2 <- 3 <- 4 <- 5

.............................................*

Now, current and next are pointing to NULL and prev is at the last node (node containing value 5)

Last step is to update the *head pointer* **hptr** to **prev** and the linked list is reversed !

Now that you've understood reversing a linked list using 3 pointers, let's try to reduce it to 2 pointers. The key in reversing the list was these 4 lines (marked in the comments) :

```
while(current!=NULL)
{
next=current->nptr; //line 1
current->nptr=prev; //line 2
prev=current; //line 3
current=next; //line 4
}
hptr=prev;
```

One thing that we know is the **current** and the **prev** pointers are definitely needed to reverse the links for every node. So we * cannot* eliminate these pointers. Can we eliminate the

**next**pointer somehow? Yes, you guessed it. We can eliminate the

**next**pointer using

**xor**.

First let's revisit the properties of **xor** operator :

We know that :

- A ^ 0 = A (Any element XOR'd with 0 is left unchanged)
- A ^ A = 0 (Any value XOR'd with itself gives 0)

Essentially, what we are trying to do is, remove the need for the extra pointer **next**. Look at line 1 and line 4 where next is being involved. Can't we just combine those lines and eliminate the next pointer ? **next** holds `current -> nptr`

. We need to temporarily store this without using a pointer.

## Implementation in C++

```
//Reverse a Linked List using 2 pointers using XOR
#include<iostream>
#include<cstdlib>
typedef uintptr_t ut;
using namespace std;
struct node
{
int data;
struct node *nptr;
};
struct node *hptr=NULL;
void insertNode(int pos, int x)
{
struct node *temp=new node;
if(temp==NULL)
cout<<"Insert not possible\n";
temp->data=x;
if(pos==1)
{
temp->nptr=hptr;
hptr=temp;
}
else
{
int i=1;
struct node* thptr=hptr;
while(i<pos-1)
{
thptr=thptr->nptr;
i++;
}
temp->nptr=thptr->nptr;
thptr->nptr=temp;
}
}
void reverseList()
{
struct node* current=hptr;
struct node* prev=NULL;
while(current!=NULL)
{
current = (struct node*)((ut)prev^(ut)current^(ut)(current->nptr)^(ut)(current->nptr=prev)^(ut)(prev=current)); //line 5
}
hptr=prev;
}
void print()
{
struct node* temp=hptr;
while(temp!=NULL)
{
cout<<temp->data<<"\n";
temp=temp->nptr;
}
}
int main()
{
insertNode(1,10);
insertNode(2,20);
insertNode(3,30);
insertNode(4,40);
insertNode(5,50);
insertNode(6,60);
insertNode(7,70);
insertNode(8,80);
insertNode(9,90);
insertNode(10,100);
reverseList();
print();
return 0;
}
```

**Output :**

```
50
40
30
20
10
```

Now, look at line 5:

```
current = (struct node*)((ut)prev^(ut)current^(ut)(current->nptr)^(ut)(current->nptr=prev)^(ut)(prev=current));
```

Let's break the expression into 5 components.

1st is `prev`

, 2nd is `current`

, 3rd is `current->nptr`

, 4th is `current->nptr=prev`

, 5th is `prev=current`

.

This expression is evaluated from **left to right**.

Compare this code with the previous version. Find any similarity? It is actually the exact same code, except that in * line 1* of the previous version we had

`next = current -> nptr`

, but here we are temporarily storing `current -> nptr`

(component 3) and *of previous version is the 4th component here.*

**line 2***of previous version is 5th component.*

**line 3**But where is the

**4th line**of previous version ?

*was*

**line 4**`current=next;`

But what does **next**contain ?

`next = current -> nptr;`

Essentially 4th line can be interpreted as

`current = current -> nptr;`

Where do you see this in this big expression ? The result after XORing the 5 components will be `current -> nptr`

which will be assigned to the LHS, **current**.

The 4 lines of the previous version are executed in the same order, but without using the next pointer.

Let us trace this using the same example :

1 -> 2 -> 3 -> 4 -> 5

current = 0 ^ 1 ^ 2 ^ 0 ^ 1

(1st component is 0 because, `prev=NULL`

and `(ut)prev`

is 0

2nd component is 1 because, `current=hptr`

initially, so `(ut)current`

is 1

3rd component is 2 because, it is the node after **current** and hence `(ut)(current->nptr)`

will be 1 more than current, that is 2

4th component is 1 because, it is nothing but **prev**

5th component is 0, because it is nothing but **current**)

Using the properties of **XOR**, we can simplify it to:

current = 2

Essentially, the 1st two and the last two components cancel each other, since any value XOR'd with itself gives 0.

We have successfully incremented the **current** pointer.(same as line 4 of previous code)

**prev** and **current** pointers are updated within this expression itself.

In the next iteration, current = 2 and prev = 1.

current = 1 ^ 2 ^ 3 ^ 2 ^ 1

Using properties of **XOR** (1^1 = 2^2 = 0) :

current = 3

**current** is incremented to the next node.

This is repeated till the last node.

Finally we update the *head pointer* **hptr**.

And the linked list is reversed !

NOTE : **line 1, line 2, line 3, line 4** of 3 pointers technique are equivalent to **line 5** of the 2 pointers technique.

## Question 1

#### In the code, why are we casting the pointers to uintptr_t type ?

## Question 2

#### In which order is the expression/ line 5 executed in the 2 pointer technique ?

With this article at OpenGenus, you must have the complete idea to reverse a linked list using 2 pointers technique using XOR operator. Enjoy.