Iteratively Reverse a Linked List Using Only 2 Pointers

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

We will be provided with a linked list, we aim to reverse the given linked list, but we are constrained to use only 2 pointers.

Consider Example:
Input Linked List:

Output Linked List:

Problem Statement Understanding

In this problem, we are given a Linked List, and we are asked to reverse the provided Linked List. We can get the desired reversed linked list by just swapping the values of nodes from front to end.

For example:
Linked List: head → 1 → 2 → 3 → 4 → 5 → NULL

So, Essentially, we can just swap the values of node such that:

  • Node 1's data with Node 5's data.
  • Node 2's data with Node 4's data.
  • Node 3's data is swapped with itself.

Our input linked list after swapping the node values will be: head → 5 → 4 → 3 → 2 → 1 → NULL.

The output linked list which we got after swapping the nodes is basically the reverse of our original linked list. Hence objective achieved.

We have already seen how to reverse a Linked List Using 3 Pointers. To read about the article, you can visit Reverse a Linked List.

In this article, we will see how we can achieve the same result using only 2 pointers.

Helpful Observation

  • If you could remember from the previous article, where we were using 3 Pointers, you can easily see that these were the 4 lines that were important for manipulating the next pointer of node:

    while(curr != NULL){
        next = curr->next; //line 1
        curr->next = prev; // line 2
        prev = curr; // line 3
        curr = next; // line 4
    

  • So here you can see that curr and prev pointers are definitely needed to reverse the node link. So we cannot eliminate these 2 pointers.

  • Now the question is can we eliminate next pointer?

    • The answer is YES, you guessed it right! We can eliminate this next Pointer. We will Use XOR to eliminate this pointer. Let's see how.

Why is XOR Used?

Let's revisit some properties of the xor(^) operator.

Following are two important properties:

  • X^0 = X (Xor of any element with 0 is the element itself).
  • X^X = 0 (Xor of any element with itself is 0).

So, Essentially with this method, we are trying to remove the need for an extra next pointer. We are temporarily storing it using the help of XOR properties.

How XOR is used?

We will use the concept of swapping two variables without using a third variable with the help of the xor operator.

  • To swap two variables x and y, without the use of a third variable, do the following :

    • x = x xor y
    • y = x xor y
    • x = x xor y
  • Also, we can write the above three lines in one line.

    • x = x ^ y ^ (y=x)

  • Similarly , if we need to swap 3 variables x,y and z, we will be required to use two swaps.

    • swap(x,y);
    • swap(y,z);
  • Swapping 3 variables x,y,z using XOR

    • x = x xor y xor z
    • y = x xor y xor z
    • z = x xor y xor z
    • x = x xor y xor z
  • Above solution in One Line. We can use any of these 3 lines to swap x,y,z.

    • z = x ^ y ^ z ^ (x=y) ^ (y=z)
    • y = x ^ y ^ z ^ (z=x) ^ (x=y)
    • x = x ^ y ^ z ^ (y=z) ^ (z=x)

We are using the same technique to swap node values in our code.

Dry Run

Implementation

#include
using namespace std;
typedef uintptr_t ut;

struct Node
{
    int data;
    struct Node *next;
    Node(int x) : data(x) , next(NULL) {}
};

Node* reverseList(Node* head_ref) {
    Node* curr = head_ref;
    Node* prev = NULL;
    while (curr != nullptr) {
        //Instead of all those 4 lines. We will write the equivalent result in 1 line.
        curr = (struct Node*)((ut)prev^(ut)curr^(ut)(curr->next)^(ut)(curr->next=prev)^(ut)(prev=curr)); //line 5
    }

    return prev;
}

void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    head = reverseList(head);
    printList(head);
    return 0;
}

Output

5 4 3 2 1

Now You must be wondering why we typecast the pointers to uintptr_t type?

  • Answer - In C++, we cannot perform bitwise operations on pointers directly, and uintptr_t is an integer type capable of holding a pointer. So we need to typecast the pointers to uintptr_t to perform xor operations here.

Code Explanation

Now, I think line 5 in the reverseList function is somewhat confusing, so let's break down this line into 5 components.

  • prev
  • curr
  • curr->next
  • curr->next = prev
  • prev = curr

The expression will be calculated from left to right.

Let us now compare this code with the one we have seen earlier using 3 Pointers. Find Any Similarity?

  • Actually, yes, this is exactly the same code we have written earlier but made some changes.
  • Earlier we had next = curr→next in line 1, here we're temporarily storing curr→next which is our 3rd component.
  • 4th Component is nothing but our line 2 of the previous code.
  • 5th Component is nothing but our line 3 of the previous code.

You must be wondering where line 4 of our previous code has gone? So line 4 was curr = next. But what does next contain?

  • It contains next = curr→next.
  • Thus, this can be interpreted as curr = curr->next, so essentially the result of all these 5 components is curr→next which will be stored in curr in LHS.

Time Complexity: O(n) where n is the number of nodes in the given LinkedList.

This blog tried to discuss the problem when we are given a linked list and we are asked to reverse it using only 2 pointers. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Partitioning a linked list around a given value and If we don’t care about making the elements of the list “stable”
Next post Squareroot(n)-th node in a Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *