7 Days With Linked List
7 Days With Linked List
7 Days With Linked List
#7daysOfAlgo
Aditya Chatterjee,
Ue Kiao, PhD
Table of Contents
Page
# Chapter Number
Day
0 Introduction to this Book 3
Day Basics of Linked List +
1 Implementation 4
Day
1 Problem 1 19
Day
2 Variant of Day 1 Problem 23
Day Find the middle element of a singly
3 Linked List 29
Day Detect a loop in a linked list (3
4 methods) 35
Day Move First Element of Linked List
5 to End 50
Day
6 Reverse a doubly linked list 56
Day Reverse a linked list using 2
7 pointers technique 63
Day
7 Conclusion 73
Day 0: Introduction to this Book
Linked List is a fundamental Data Structure and an alternative to Array.
Despite being a simple Data Structure, problems involving it can be
challenging. With practice and correct way of thinking, you can master it
easily and know when to use it in real life problems.
We will attempt one problem every day in this week and analyze each
problem deeply.
Our schedule:
Day 1: Basics of Linked List + Implementation + Problem 1
Day 2: Variant of Day 1 Problem
Day 3: Find the middle element of a singly Linked List
Day 4: Detect a loop in a linked list (3 methods)
Day 5: Move First Element of Linked List to End
Day 6: Reverse a doubly linked list
Day 7: Reverse a linked list using 2 pointers technique
On following this routine sincerely, you will get a strong hold on Linked List
quickly and will be able to attempt interview and real-life problems easily.
#7daysOfAlgo: a 7-day investment to Algorithmic mastery.
Some of our other nice books on Algorithms:
Array
Linked List
The first way is to store the elements of the list in an array but arrays have
restrictions and disadvantages.
The second way of maintaining a list in memory is through linked list. Let us
study what a linked list is and after that we will come to know how it
overcomes the limitations of array.
There are several modifications of Linked List which finds use in various
basic and advanced applications. We will explore Singly Linked List and you
will get the basics of the other types as well.
Singly Linked List is a variant of Linked List which allows only forward
traversal of linked list. This is the simplest form of Linked List, yet it is
effective for several problems such as Big Integer calculations.
We will look into how various operations are performed and the advantages
and disadvantages.
Singly Linked List
A singly linked list is made up of nodes where each node has two parts:
Note: Using NULL is not a good coding standard but it remains the most
common implementation technique. We will look into how to avoid using
NULL nodes at a later chapter in this book.
NULL is not good because it results in several runtime errors if not handled
correctly.
Visualize this image to understand the idea of Singly Linked List:
START variable
First node, Second node, Third node
Third node is the last node.
Representation of Singly Linked List:
A Singly linked list is represented by a pointer to the first node of the linked
list. The first node is called head or start.
If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
data
pointer to the next node
In C, we can represent a node using structures.
In Java, LinkedList can be represented as a class and a Node as a separate
class. The LinkedList class contains a reference of Node class type.
Complexity of different operations:
Complexity of Insertion operation in a Linked List:
struct node
{
int data;
struct node *next;
};
int data is the data part of the node which will hold the data.
struct node * next is the pointer variable of node datatype.
struct node * p defines start as a variable which can store the address
of the node.
p is a pointer variable which is used to create memory block in
RAM.
p can be viewed as our Linked List as it is the starting node and the
entire Linked List can be accessed using it.
So, in this approach, when we need to add a second node (say P2) to the first
node (say P1), then we do as follow (provided both P1 and P2 exists):
P1.next = P2;
With this, you have the basic idea of how to create a Linked List structure in
C.
Note the Node class is private. This is because we do not want the
node object to be created by other applications like a Binary Tree
data structure. This Node class will be a private class of Linked List
class and hence, only the Linked List class can create Node objects.
This is the right way as node are the building blocks of Linked List.
We have two data members: item and next (another Node object).
We have the constructor defined which is initializing the item and
next node.
The above node class will be the private class of a Linked List class which is
as follows:
class LinkedList<E>
{
private static class Node<E>
{
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next)
{
this.item = element;
this.prev = prev;
this.next = next;
}
}
int size = 0;
Node<E> first;
It has the Node class as a private class. Nodes are the building blocks
of a Linked List.
E is the data type template which can be a standard data type like int
or an user defined data type.
There are 2 attributes of the Linked List class: size and first.
size stores the total size of the Linked List. In practice, one can
calculate the size provided the first node is given but it is a good
practice to store important information (like size) for instant access.
Using size attribute, size of Linked List is fetched in O(1) time while
getting the size using first node takes O(N) time as we need to
traverse the entire Linked List.
We define an empty constructor.
Based on this, we will have an add function with the Linked List class which
is used to create a sample Linked List like:
public class Test_LinkedList
{
public static void main()
{
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(10);
ll.add(9);
ll.add(100);
}
}
Note:
search(head, x)
1) If head is NULL, return false.
2) If head's key is same as x, return true;
2) Else return search(head->next, x)
Complexity
E unlinkLast(Node<E> l)
{
final E element = l.item;
final Node<E> newLast = l.prev;
l.prev = null;
l.item = null;
last = newLast;
if(newLast == null)
first = null;
else
newLast.next = null;
-- size;
return element;
}
With this, you have a strong idea of how to delete any node in a Linked List.
Deletion is an advantage of Linked List over array.
Complexity
Pseudocode
Let the input linked list be sorted in increasing order.
STEP 1: Define a node with the new element (say N1)
STEP 2: If Linked list is empty, then make the node N1 as head and return it.
STEP 3: If value of the node to be inserted is smaller than value of head
node, then insert the node at start and make it head. If condition of STEP 3 is
false, then move to STEP 4.
STEP 4: Find the appropriate node after which the input node is to be
inserted. To find the appropriate node start from head, keep moving until we
reach a node whose value is greater than the input node. The node just before
the node is the appropriate node.
STEP 5: Insert the node after the appropriate node found in STEP 4.
void sortedInsert(E e)
{
Node current = first;
/* Special case for head node */
if (current == null || current.data >= e)
{
LinkFirst(e);
}
else
{
while (current.next != null &&
current.next.data < new_node.data)
current = current.next;
Node<E> newNode = new Node<>(current, e, current.next);
}
}
Complexity
Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(1)
Space complexity: Θ(1)
Yes, binary search can be used in Linked List but the performance will be
linear O(N) and not O(logN).
Ideas applicable for array may not hold true for Linked List.
Random access is not possible in Linked List. It takes linear time
O(N).
Linear Search is better than Binary Search for Linked List.
Think of these ideas and we will attempt another problem on Linked List
tomorrow.
Day 2: Sort a Linked List which is
already sorted on absolute values
The problem at hand is to sort a singly Linked List which is already sorted on
absolute value. Sorting always takes a time complexity of O(N log N) and in
this case, we will be utilizing our knowledge of the data within the Linked
List to sort it in O(N) time complexity.
Depending on the sorting algorithm you will choose, the complexity will be:
* Time Complexity: O(N logN)
* Space Complexity: O(1) or O(N)
Considering the information from the problem statement that the values are
sorted in absolute value, we might be able to achieve better performance.
Algorithm
Key idea: Positive values are already sorted, and negative values are sorted in
reverse order
The steps to solve this problem are:
Example
Initial data: 5 1 -3 2 4 9 10 0 -11 -2
Data sorted on absolute value: 0 1 -2 -3 4 5 9 10 -11
Traverse it from the front and stop when a negative value is encountered
Negative value found: -2 : Delete the node and append it to the front
Data currently: -2 0 1 -3 4 5 9 10 -11
Negative value found: -3 : Delete the node and append it to the front
Data currently: -3 -2 0 1 4 5 9 10 -11
Negative value found: -11 : Delete the node and append it to the front
Data currently: -11 -3 -2 0 1 4 5 9 10
End of Linked List encountered
Data is sorted
Sorted data: -11 -3 -2 0 1 4 5 9 10
Complexity
Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(N)
Space complexity: Θ(1)
class Sort_Linked_List
{
static Node head;
static class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node sortedList(Node head)
{
Node prev = head;
Node curr = head.next;
while(curr != null)
{
if(curr.data < prev.data)
{
prev.next = curr.next;
curr.next = head;
head = curr;
curr = prev;
}
else
{
prev = curr;
curr = curr.next;
}
}
return head;
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
}
If we have some information about the input data, then to sort the
data we may not need standard sorting algorithms.
Moving an element to the front takes O(1) in Linked List and O(N)
in an array.
This problem brings out the power of Linked List compared to array.
Day 3: Find the middle element of a
singly Linked List
The problem we are exploring is to find the middle element of a singly linked
list. For instance, if the linked list is 1 -> 2 -> 3 -> 4 -> 5, then the middle
element is 3. If there are even number of elements in a linked list such as 1 ->
2 -> 3 -> 4 -> 5 -> 6, then the middle element is 3 and 4.
// one traversal
int count_elements(Node head)
{
int count = 0;
if(head != null) ++ count;
Node temp = head;
while(temp.next != null)
{
++ count;
temp = temp.next;
}
return count;
}
// second traversal
int middle_element(int count, Node head)
{
int middle = (int)count/2;
Node temp = head;
while(middle > 0)
{
temp = temp.next;
-- middle;
}
Complexity
Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(N)
Space complexity: Θ(1)
Pseudocode
The pseudocode of the algorithm to find the middle element using one
traversal is as follows:
// one traversal
int middle_element(Node head)
{
Node first_node = head, second_node = head;
Complexity
Worst case time complexity: Θ(N)
Average case time complexity: Θ(N)
Best case time complexity: Θ(N)
Space complexity: Θ(1)
class LinkedList
{
Node head; // head of linked list
private class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void middle_element()
{
Node pointer_1 = head;
Node pointer_2 = head;
if(head == null) return;
while (pointer_2 != null && pointer_2.next != null)
{
pointer_2 = pointer_2.next.next;
pointer_1 = pointer_1.next;
}
System.out.println("The middle element is " + pointer_1.data );
}
public void add(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
public void print_list()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+"->");
temp = temp.next;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
LinkedList list = new LinkedList();
for (int i=0; i<=10; i++)
{
list.add(i);
list.print_list();
list.middle_element();
}
}
}
Steps:
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
int marked;
node* next;
};
node* head=NULL;
class Linkedlist
{
public:
void insertnode(int value)
{
node* new_node=new node();
new_node->data=value;
new_node->marked=0;
if(head==NULL)
head=new_node;
else
{
new_node->next=head;
head=new_node;
}
}
void createloop()
{
node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=head;
}
int detectloop()
{
while(head->next!=NULL)
{
head->marked=head->marked+1;
head=head->next;
if(head->marked>1)
{
cout<<"loop"<<endl;
return 1;
}
return 0;
}
};
int main()
{
Linkedlist obj;
int a;
//insert nodes in linkedlist
obj.insertnode(3);
obj.insertnode(9);
obj.insertnode(7);
obj.insertnode(4);
obj.insertnode(5);
//create loop for testing
obj.createloop();
// detect loop
a=obj.detectloop();
head=NULL;
obj.insertnode(6);
obj.insertnode(7);
obj.insertnode(9);
obj.insertnode(10);
obj.insertnode(11);
a=obj.detectloop();
if(!a)
cout<<"no loop"<<endl;
Output:
loop
no loop
Using HashMap
In this approach, we traverse the list and insert the address of each node into
the hash map. If there is a loop in the linked list, then at some point, the next
of the current node will point to the previously stored node in the hash map.
If there is no loop, then when the whole list is traversed, NULL is reached (as
the last node) false will be returned or else true will be returned.
Steps:
Visit each node of the linked list one by one and put address of each
node in a Hash Table.
If the current node is already present in the Hash Map, then there is a
loop.
If we reach the last node (such that next pointer is NULL), then there
is no loop.
Implementation of Hashing method
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* next;
};
node* head=NULL;
class Linkedlist
{
public:
void insertnode(int value)
{
node* new_node=new node();
new_node->data=value;
if(head==NULL)
head=new_node;
else
{
new_node->next=head;
head=new_node;
}
}
void createloop()
{
node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=head;
}
bool detectloop()
{
set<node*> s;
while (head != NULL) {
//if node is alreay in the hash
//then there is a loop hence return
//true
if (s.find(head) != s.end())
return true;
head = head->next;
}
return false;
}
};
int main()
{
Linkedlist obj;
//insert nodes in linkedlist
obj.insertnode(3);
obj.insertnode(9);
obj.insertnode(7);
obj.insertnode(4);
obj.insertnode(5);
//create loop for testing
obj.createloop();
// detect loop
bool a=obj.detectloop();
if(a)
cout<<"Loop Found"<<endl;
else
cout<<"Loop not Found"<<endl;
head=NULL;
obj.insertnode(9);
obj.insertnode(10);
obj.insertnode(11);
obj.insertnode(12);
obj.insertnode(13);
bool b=obj.detectloop();
if(b)
cout<<"Loop found"<<endl;
else
cout<<"Loop not found"<<endl;
Output:
Loop Found
Loop not found
if(head==NULL)
head=new_node;
else
{
new_node->next=head;
head=new_node;
}
}
void createloop()
{
node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=head;
}
int detectloop()
{
node* slow=head;
node* fast=head;
while(slow && fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
cout<<"Loop Found"<<endl;
return 1;
}
// detect loop
obj.detectloop();
Output:
Loop Found
Loop not found
1. This is the initial state of the algorithm, where slow and fast both the
pointer points to the head of the linked list.
2. At the second step of the algorithm, the slow pointer moves by one
node and the fast pointer moves by two nodes. so now slow is at 2
and fast is at 3.
3. At the third step of the algorithm, the loop continues and now slow is
at 3 and fast is at 5.
4. At the fourth step of the algorithm, the slow pointer is at 4 and now
fast pointer is at 3.
5. This is the fifth and the last step of the algorithm, in this step slow moves
by one node and fast moves by two so now both points to the node 5.
Question
If a Linked list has only a single node, can it contain a loop?
Yes, it can contain a loop if the node points back to itself. that means if the
next of the node points back to itself.
With this, we have explored three approaches to detect a loop. The key point
you must note:
The slow and fast pointer technique which efficiently solved our previous
problem for finding the middle node of Linked List, has been used to solve
our current problem (detecting loop) efficiently.
Both are distinct problems based on problem statement, yet the solution is
same.
Think on this idea.
Day 5: Move First Element of Linked
List to End
In this problem, given a linked list, we move the first element of the linked
list to the end of the linked list.
Example input:
1 -> 2 -> 2 -> 3
Example output:
2 -> 2 -> 3 -> 1
Note: The element 1 has been moved to the end of the Linked List.
Brute Force
In Brute Force approach, we swap the data values of two adjacent nodes one
by one till the first node reaches the last position.
Steps:
Pseudocode:
for i = 0 to N-1
swap(node(i), node(i+1))
This approach has an O(N) time complexity. We can reduce the number of
operations performed in the efficient approach though the Time Complexity
will remain same. Swaps are expensive operations.
Solution Approach
In this solution approach we maintain two pointers. The algorithm is as
follows:
STEP 1: Two pointers, the "first" pointer and the "last" pointer are
maintained.
STEP 2: Both of them initially contain reference to the head.
STEP 3: We traverse the Linked List using "last" pointer and "last" pointer is
made to point to the last node of the Linked List.
STEP 4: The next element after the head is made the new head by moving
the head reference to the next of current head.
STEP 5: The next of the last pointer points to the previous head and it's
"next" stores "null".
Pseudocode:
// Update head
HEAD = HEAD->next;
#include <bits/stdc++.h>
using namespace std;
//node representation
struct node {
int data;
struct node* next;
};
//pointer declaration
struct node* head;
struct node* tail = new node;
struct node* temp = new node;
struct node* curr;
struct node* pre;
int main(){
int n, num, key;
cout << "Enter the number of elements" <<endl;
cin >> n ;
head tail
1 -> 3 -> 2 -> 3
Initially the head_pointer pointer would be storing the address of the head or
the first element of the linked list.
The first and last pointers are also initialized.
head tail
1 -> 3 -> 2 -> 3
The head_pointer then points to the next element after the head. We make the
next of head as our new head now.
head tail
1 -> 3 -> 2 -> 3
Now tail is moved to the first element and it's next stores null. The structure
of the list now becomes as follows
head tail
3 -> 2 -> 3 -> 1
Time complexity:
The time complexity of this approach is O(N)
where, N is the number of nodes in the linked list. As we traverse all the N
nodes in one pass, this is done to reach the tail pointer. The space complexity
is O(1) as extra space is not allocated during this process.
Space Complexity: O(1).
Day 6: Reverse a Doubly Linked List
We are going to see how to reverse a doubly linked list by reversing the links
of each node (without swapping values of nodes).
Introduction to Doubly Linked List
A doubly linked list is a linear data structure which is a linked list which
contains an extra pointer to store the address of the previous node. It is a
variation of singly linked list. In singly linked list, only forward traversal is
possible, whereas in doubly linked list, forward and backward traversal is
possible.
Structure of a Doubly Linked List
A double linked list contains two pointers : a pointer to store the address of
the next node (same as in singly linked list) and a pointer to store the address
of the previous node. The structure of the doubly linked list also contains a
field to store the data of the node.
struct node
{
int data;
struct node *nptr; //next pointer
struct node *pptr; //previous pointer
};
Node 1's previous pointer should be NULL and next pointer should point to
Node 2.
Node 2's previous pointer should point to Node 1 and next pointer should
point to Node 3.
Node 3's previous pointer should point to Node 2 and next pointer should
point to Node 4.
Node 4's previous pointer should point to Node 3 and next pointer should
point to Node 5.
Node 5's previous pointer should point to Node 4 and next pointer should be
NULL.
Output
We need to reverse both the links of every node of the doubly linked list.
That is,
Node 1's previous pointer should point to Node 2 and next pointer be NULL.
Node 2's previous pointer points to Node 3 and next pointer points to Node 1.
Node 3's previous pointer points to Node 4 and next pointer points to Node 2.
Node 4's previous pointer points to Node 5 and next pointer points to Node 3.
Node 5's previous pointer points be NULL and next pointer points to Node 4.
Steps to do this:
STEP 1: For each node P in Linked List
STEP 1.1: Node next_original = P.next
STEP 1.2: P.next = P.previous
STEP 1.3: P.previous = P.next
STEP 2: The entire Linked List is reversed.
In short: First reverse the previous and next pointers of the doubly linked list.
We would have to make the previous pointer to point the next node (instead
of the previous node) and the next pointer to point to the previous node
(instead of the next node).
struct node
{
int data;
struct node *nptr; //next pointer
struct node *pptr; //previous pointer
};
if(pos==1)
{
hptr=hptr->nptr;
}
else
{
int i=1;
struct node *thptr=hptr;
while(pos<i-1)
{
thptr=thptr->nptr;
}
thptr->nptr=thptr->nptr->nptr;
if(thptr->nptr!=NULL)
thptr->nptr->pptr=thptr;
}
}
}
void reverseList()
{
struct node *current=hptr;
struct node *prev=NULL;
while(current!=NULL)
{
current->pptr=current->nptr; //line 1
current->nptr=prev; //line 2
prev=current; //line 3
current=current->pptr; //line 4
}
hptr=prev;
}
void print()
{
struct node *thptr=hptr;
while(thptr!=NULL)
{
cout<<thptr->data<<"\n";
thptr=thptr->nptr;
}
}
int main()
{
insertNode(1,11);
insertNode(2,12);
insertNode(3,13);
insertNode(4,14);
insertNode(5,15);
reverseList();
print();
return 0;
}
Output:
15
14
13
12
11
Explanation of code:
Let us look at the reverseList() function.
We use 2 pointers, current and prev for the link reversal.
Lines 1, 2, 3 and 4 are the key in reversing the links of every node.
Line 1 makes the current node's previous pointer point to its next node (link
reversal)
Line 2 makes the current node's next pointer point to its previous node(link
reversal)
Line 3 updates the prev pointer for link reversal of next node
Line 4 updates the current pointer for link reversal of next node
After every node gets its links reversed, we have one last thing to do :- update
the head pointer.
At the end of the while loop, current becomes NULL and prev points to the
last node (last node of input list). So, in our reversed list, the last node would
be the first node, so we update the head pointer as prev.
And the doubly linked list is reversed !
Input :
1 -> 2 -> 3 -> 4 -> 5
^
Our objective is to reverse the linked list by reversing its links
Expected Output :
1 <- 2 <- 3 <- 4 <- 5
..............................^
Before we dive into 2 pointer technique, let us take a look at the 3 pointer
technique to reverse a linked list.
Implementation in C++
struct node
{
int data;
struct node *nptr;
};
struct node *hptr=NULL;
void reverseList()
{
struct node* current=hptr;
struct node* next;
struct node* prev=NULL;
while(current!=NULL)
{
next=current->nptr; //line 1
current->nptr=prev; //line 2
prev=current; //line 3
current=next; //line 4
}
hptr=prev;
}
void print()
{
struct node* temp=hptr;
while(temp!=NULL)
{
cout<<temp->data<<"\n";
temp=temp->nptr;
}
}
int main()
{
insertNode(1,10);
insertNode(2,20);
insertNode(3,30);
insertNode(4,40);
insertNode(5,50);
reverseList();
print();
return 0;
}
Output:
50
40
30
20
10
next pointer
current pointer
prev pointer
Our objective is to iterate over every node and make it point to the previous
node (reverse every node's link). Sounds simple right ?
Let us take the same example of the linked list
1 -> 2 -> 3 -> 4 -> 5 -> NULL
We need to reverse the link of every node, that is, make 1 to point to NULL,
2 to point to 1, 3 to point to 2, 4 to point to 3, and 5 to point to 4 and at last
make head pointer point to the node containing value 5.
NULL <- 1 <- 2 <- 3 <- 4 <- 5
What should we do to get achieve this link reversal?
We need to make the current node point to the previous node (link reversal).
Let us try that.
Also remember that current is pointing to the 1st node (current = hptr) and
prev is pointing to NULL.
At first my current is pointing to node with value 1
1 -> 2 -> 3 -> 4 -> 5
^
If I make current->nptr = prev, that will result in :
1 -> NULL, 2 -> 3 -> 4 -> 5
NOTE : The link between node 1 and node 2 is lost when node 1 points to
NULL. A node cannot point to 2 different locations.
Now, the head pointer is pointing to node containing 1 and the rest of the list
is lost (we do not have any reference to the list and hence cannot access it and
is lost!)
We do not want this to happen . So, we bring in another pointer next to have
a reference to the list.
Before we make current->nptr = prev (reversal of link), we first update the
next pointer as next=current->nptr;
( * is prev , ^ is current , and $ is next)
1 -> 2 -> 3 -> 4 -> 5
^.....$
current->nptr = prev
prev = current;
current = next;
End of Iteration 1 :
1 -> NULL , 2 -> 3 -> 4 -> 5
*..................^$
Keep repeating this procedure until the last node.
End of Iteration 2 :
NULL <- 1 <- 2 , 3 -> 4 -> 5
.......................*..^$
End of Iteration 3 :
NULL <- 1 <- 2 <- 3 , 4 -> 5
..............................*...^$
End of Iteration 4 :
NULL <- 1 <- 2 <- 3 <- 4 , 5
.....................................*...^$
End of Iteration 5 :
NULL <- 1 <- 2 <- 3 <- 4 <- 5
.............................................*
Now, current and next are pointing to NULL and prev is at the last node
(node containing value 5)
Last step is to update the head pointer hptr to prev and the linked list is
reversed !
Now that you have understood reversing a linked list using 3 pointers, let's
try to reduce it to 2 pointers. The key in reversing the list was these 4 lines
(marked in the comments) :
while(current!=NULL)
{
next=current->nptr; //line 1
current->nptr=prev; //line 2
prev=current; //line 3
current=next; //line 4
}
hptr=prev;
One thing that we know is the current and the prev pointers are definitely
needed to reverse the links for every node. So, we cannot eliminate these
pointers. Can we eliminate the next pointer somehow? Yes, you guessed it.
We can eliminate the next pointer using XOR.
First let us revisit the properties of XOR operator :
We know that :
A ^ 0 = A (Any element XOR'd with 0 is left unchanged)
A ^ A = 0 (Any value XOR'd with itself gives 0)
Essentially, what we are trying to do is, remove the need for the extra pointer
next. Look at line 1 and line 4 where next is being involved. Can't we just
combine those lines and eliminate the next pointer?
next holds current -> nptr. We need to temporarily store this without using a
pointer.
Implementation in C++
//Reverse a Linked List using 2 pointers using XOR
#include<iostream>
#include<cstdlib>
typedef uintptr_t ut;
using namespace std;
struct node
{
int data;
struct node *nptr;
};
struct node *hptr=NULL;
void reverseList()
{
struct node* current=hptr;
struct node* prev=NULL;
while(current!=NULL)
{
current = (struct node*)((ut)prev^(ut)current^(ut)(current->nptr)^(ut)(current-
>nptr=prev)^(ut)(prev=current)); //line 5
hptr=prev;
}
void print()
{
struct node* temp=hptr;
while(temp!=NULL)
{
cout<<temp->data<<"\n";
temp=temp->nptr;
}
}
int main()
{
insertNode(1,10);
insertNode(2,20);
insertNode(3,30);
insertNode(4,40);
insertNode(5,50);
insertNode(6,60);
insertNode(7,70);
insertNode(8,80);
insertNode(9,90);
insertNode(10,100);
reverseList();
print();
return 0;
}
Output:
50
40
30
20
10
With this, you must have a very strong hold on Linked Lists. Moving from 3
pointers to 2 pointers may not seem to be much improvement but this is
important because: