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 :

1. A ^ 0 = A (Any element XOR'd with 0 is left unchanged)
2. 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 line 2 of previous version is the 4th component here.line 3 of previous version is 5th component.
But where is the 4th line of previous version ? line 4 was 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.

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