Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Iteratively Reverse a Linked List Using Only 2 Pointers

Last Updated on March 10, 2022 by Ria Pathak

### 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:

### 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.

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

• 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

#include <stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef uintptr_t ut;

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

/* Function to reverse the linked list using 2 pointers */
{
struct Node* prev = NULL;

// at last prev points to new head
while (current != NULL) {
// This expression evaluates from left to right
// current->next = prev, changes the link from
// next to prev node
// prev = current, moves prev to current node for
// next reversal of node
// This example of list will clear it more 1->2->3->4
// initially prev = 1, current = 2
// Final expression will be current = 1^2^3^2^1,
// as we know that bitwise XOR of two same
// numbers will always be 0 i.e; 1^1 = 2^2 = 0
// After the evaluation of expression current = 3 that
// means it has been moved by one node from its
// previous position
current = (struct Node*)((ut)prev ^ (ut)current ^ (ut)(current->next) ^ (ut)(current->next = prev) ^ (ut)(prev = current));
}

}

/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

/* put in the data  */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
{
while (temp != NULL) {
printf("%d  ", temp->data);
temp = temp->next;
}
}

/* Driver program to test above function*/
int main()
{

return 0;
}

while (current != null)
{
Node next = current.next; //line 1
current.next = prev; //line 2
prev = current; //line 3
current = next; //line 4
}

while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next

• 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.

### Implementation

#include
using namespace std;
typedef uintptr_t ut;

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

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()
{

return 0;
}
#include
#include
#include
typedef uintptr_t ut;

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

/* Function to reverse the linked list using 2 pointers */
{
struct Node* next;
while (current->next != NULL) {
next = current->next;
current->next = next->next;
}
}

/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
}

/* Function to print linked list */
{
while (temp != NULL) {
printf("%d  ", temp->data);
temp = temp->next;
}
}

/* Driver program to test above function*/
int main()
{

return 0;
}
class IterativeReverse
{
static class Node
{
int data;
Node next;
};

static void reverse()
{
Node prev = null;

// At last prev points to new head
while (current != null)
{
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
}
static void push(int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
}
static void printList()
{
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String []args)
{
push(1);
push(2);
push(3);
push(4);
push(5);

printList();
reverse();
printList();
}
}

class node:A

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def reverse(self):
prev = None
while(current is not None):
next, current.next = current.next, prev
prev, current = current, next

def push(self, new_data):
new_node = node(new_data)

def printList(self):
while(temp):
print (temp.data,end=" ")
temp = temp.next

llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

llist.reverse()
llist.printList()

#### 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.

[forminator_quiz id=”4610″]

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.