Last Updated: Mar 27, 2024

# Using only 2 pointers reverse a Linked List

## Introduction

Linked List is one the most asked data structures that recruiters tend to ask about in technical interviews. Not only does it test the pointer knowledge of a candidate, but also his/her analytical and reasoning skills.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

## Problem Statement

Given a singly Linked List, reverse the Linked List using 2(two) pointers only.

According to the question, you will be given a Linked List, specifically a singly Linked List. You are supposed to return the reverse of that Linked List.

But the catch here is that you are supposed to reverse it using only two-pointers. The question explicitly specifies how you have to implement the approach.

### Example

If the given Linked List is as follows:

Then, the reversed Linked List is as follows:

## Approach 1: Iterative Approach

Here is the core logic we have used to reverse the LinkedList with three-pointers for the next node (*next), the previous node (*prev), and the current node (*current).

``````void reverse(struct node **head_ref)
{
struct node *next = NULL;
struct node *prev = NULL;
while(current != NULL)
{
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
}``````

For, using only 2 (two) pointers, we need to eliminate the (*next) pointer. For that, we can swap the pointers using the XOR operation. XOR operator has the following properties, which we will use:

• XORing 0 with any element leaves it unchanged

• In XORing any value with itself, A ^ A = 0.

Using this method, we are attempting to remove the need for an additional next pointer. The XOR property is used to store it temporarily. With the help of the xor operator, we will swap two variables without using a third variable.

Bitwise operations cannot be performed on pointers directly in C++, and uintptr_t is a type that holds a pointer. Therefore, we need to typecast these pointers to uintptr_t to perform the XOR operation.

Consider the following scenario:

Let prev and curr be pointers to two adjacent nodes in a Linked List. Now, let’s understand the expression below:

``curr = (struct Node *)((ut)prev ^ (ut)curr ^ (ut)(curr->next) ^ (ut)(curr->next = prev) ^ (ut)(prev = curr));``

In the above expression, we are achieving the following operations:

1. Assigning curr->next to prev pointer in the fourth term.

2. Assigning prev to the curr pointer in the fifth term.

3. Also, if you look closely we are effectively doing the following operation (A represents curr, B represents prev and C represents curr->next ):
A = B ^ A ^ C ^ B ^ A => A = C

4. Thus, we are moving one node ahead as a result of this expression.

### Algorithm

Step 1: Create a reverse() function which passes the head reference value.

Step 2: Initialize two pointers as current node pointer as (curr = first), previous node pointer as (prev = NULL).

Step 3: Enter the While loop and run the loop until the curr is equal to NULL, then,

Write an equation for curr to store the bitwise calculation we have discussed above.

``curr = (struct Node *)((ut)prev ^ (ut)curr ^ (ut)(curr->next) ^ (ut)(curr->next = prev) ^ (ut)(prev = curr));``

Step 4: End the while loop and return the prev value.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
typedef uintptr_t ut;

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

void printData(Node *node)
{
while (node != NULL)
{
cout << node->data;
if (node->next != NULL)
cout << " -> ";
node = node->next;
}
}

Node *reverse(Node *first)
{
Node *curr = first;
Node *prev = NULL;
while (curr != NULL)
{
// As discussed above.
curr = (struct Node *)((ut)prev ^ (ut)curr ^ (ut)(curr->next) ^ (ut)(curr->next = prev) ^ (ut)(prev = curr));
}
return prev;
}

int main()
{

cout << "\nReversed Linked List: ";
return 0;
}``````

Output

``````Original Linked List: 10 -> 53 -> 13 -> 43 -> 52
Reversed Linked List: 52 -> 43 -> 13 -> 53 -> 10 ``````

#### Time Complexity Analysis

It is O (N). Here, N is the number of nodes in the Linked List.

#### Space Complexity Analysis

It is O (1) as no extra space is required.

Note: The method appears to be promising, but it may not have any practical advantages in terms of space or memory compared to non-recursive functions using three-pointers.

## Approach 2

With this approach, we try to reduce the amount of space we use for implementation.

### Algorithm

Step 1: Create a reverse() function which passes an indirect reference named first.

Step 2: Initialize 2 pointers first is curr = *first, and the second is the next pointer.

Step 3: Enter the while loop and do the following operations:

``````next = curr->next;
curr->next = next->next;
next->next = (*first);
*first = next;``````

Step 4: End while loop

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

struct Node
{
int data;
struct Node *next;
};

{
struct Node *new_node = new Node;
new_node->data = new_data;
}

{
while (temp != NULL)
{
printf("%d", temp->data);
if (temp->next != NULL)
{
printf(" -> ");
}
temp = temp->next;
}
}

// reverse function
void reverse(struct Node **first)
{
struct Node *curr = *first;
struct Node *next;
while (curr->next != NULL)
{
next = curr->next;
curr->next = next->next;
next->next = (*first);
*first = next;
}
}

int main()
{
return 0;
}``````

Output

``````Original Linked List: 52 -> 43 -> 13 -> 53 -> 10
Reversed Linked list: 10 -> 53 -> 13 -> 43 -> 52``````

#### Time Complexity Analysis

It is O (n) as every node is visited for updating the pointer.

#### Space Complexity Analysis

It is O (1) as we do not use any extra space, therefore space used can be considered constant.

Must Read  C Program to Reverse a Number

### Can a singly Linked List be reversed with time complexity less than O(n)?

Reversing a simple single-linked list will take more than O(n) time. Reversing a singly linked list will take O(n) time using recursive and iterative methods. Swapping the head and tail pointers makes it possible to reverse a memory-efficient double-linked list in O(1) time.

### What is the difference between * and **?

* is a pointer that points to a variable holding a value whereas ** represents a pointer to another pointer variable.

### Describe struct node *.

The structure node* represents an element of a structure node. It generally stores the address of variables of type 'node,' which is a custom structure. Using the struct before node* is needed to comply with C syntax.09 Use struct before node* in the program.

## Conclusion

This article extensively discusses the programming problem: Using only 2 pointers reverse a Linked List in detail. It goes on to mention the pseudocode, implementation, and time trade-offs.

Recommended Problems -

We hope that this blog has helped you enhance your knowledge regarding Using only 2 pointers to reverse a Linked List, and if you would like to learn more, check out our articles on Coding Ninjas Blogs
You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, and many more!

If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the ProblemsInterview Experiences, and Interview Bundle for placement preparations.

Nevertheless, you may consider our Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow.

Happy Coding!

Topics covered
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 1: Iterative Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity Analysis
3.2.2.
Space Complexity Analysis
4.
Approach 2
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Time Complexity Analysis
4.2.2.
Space Complexity Analysis
5.