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;
struct node *current = (*head_ref);
while(current != NULL)
{
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
(*head_ref) = prev;
}
You can also try this code with Online C++ Compiler
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:
-
Assigning curr->next to prev pointer in the fourth term.
-
Assigning prev to the curr pointer in the fifth term.
-
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
- 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));
You can also try this code with Online C++ Compiler
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()
{
Node *head = new Node(10);
head->next = new Node(53);
head->next->next = new Node(13);
head->next->next->next = new Node(43);
head->next->next->next->next = new Node(52);
cout << "Original Linked List: ", printData(head);
head = reverse(head);
cout << "\nReversed Linked List: ";
printData(head);
return 0;
}
You can also try this code with Online C++ Compiler
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;
};
// adding node to the Linked List
void add(struct Node **head_ref, int new_data)
{
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// printing the Linked List
void printList(struct Node *head)
{
struct Node *temp = head;
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()
{
struct Node *head = NULL; // adding elements in the LinkedList
add(&head, 10);
add(&head, 53);
add(&head, 13);
add(&head, 43);
add(&head, 52); // printing the elements of the LinkedList
printf("Original Linked List: ");
printList(head);
reverse(&head);
printf("\nReversed Linked list: ");
printList(head);
return 0;
}
You can also try this code with Online C++ Compiler
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
Frequently Asked Questions
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.
To hold a tighter grip on the topic, we recommend reading more articles related to the same topic: Applications of Linked List, Advantages and Disadvantages of Linked List, and Binary Search on Linked List.
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 Algorithms, Competitive Programming, JavaScript, SQL, System 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 Problems, Interview 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!
116+ registered 