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!
Linked list articles

Iteratively Reverse a Linked List Using Only 2 Pointers

PrepBytes

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

    #include <stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef uintptr_t ut;
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* Function to reverse the linked list using 2 pointers */
void reverse(struct Node** head_ref)
{
    struct Node* prev = NULL;
    struct Node* current = *head_ref;
 
    // 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));
    }
 
    *head_ref = prev;
}
 
/* 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 */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Function to print linked list */
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
 
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 85);
 
    printf("Given linked list\n");
    printList(head);
    reverse(&head);
    printf("\nReversed Linked list \n");
    printList(head);
    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.

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;
}

#include 
#include 
#include
typedef uintptr_t ut;
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* Function to reverse the linked list using 2 pointers */
void reverse(struct Node** head_ref)
{
    struct Node* current = *head_ref;
    struct Node* next;
    while (current->next != NULL) {
        next = current->next;
        current->next = next->next;
        next->next = (*head_ref);
        *head_ref = 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;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
/* Function to print linked list */
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
 
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 85);
 
    printf("Given linked list\n");
    printList(head);
    reverse(&head);
    printf("\nReversed Linked list \n");
    printList(head);
    return 0;
}

class IterativeReverse
{
    static class Node
    {
	    int data;
	    Node next;
    };
    static Node head_ref = null;

    static void reverse()
    {
	    Node prev = null;
	    Node current = head_ref;
	
	    // At last prev points to new head
	    while (current != null)
	    {
	    	Node next = current.next;
		    current.next = prev;
		    prev = current;
		    current = next;
	    }
	    head_ref = prev;
    }
    static void push(int new_data)
    {
	    Node new_node = new Node();
	    new_node.data = new_data;
	    new_node.next = (head_ref);
	    (head_ref) = new_node;
    }
    static void printList()
    {
	    Node temp = head_ref;
	    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);

	    System.out.print("Given linked list\n");
	    printList();
	    reverse();
	    System.out.print("\nReversed Linked list \n");
	    printList();
    }
}




class node:A

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

class LinkedList:

	def __init__(self):
		self.head = None

	def reverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next, current.next = current.next, prev
			prev, current = current, next
		self.head = prev
		
	def push(self, new_data):
		new_node = node(new_data)
		new_node.next = self.head
		self.head = new_node

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


llist = LinkedList()
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.

Leave a Reply

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

Close

Related Post