by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Few of the functions used below are explained in Linked List Insert operation, Linked List Delete Operation and Linked List Traverse and Search article . Refer those before moving ahead.
Loop in a Linked List
If in a Linked List, two nodes has same next pointer then it will create a cycle in Linked List which means loop is present in Linked list. In this case if we traverse the Linked List, NULL will never be found and it will keep on traversing in the same loop infinitely.
As shown in Below image, node 3 and node 7 has same next pointer 4. As you can see in the image there is no node which is pointing to NULL and hence traversal will result in infinitely rotating in the Linked List loop.
Breaking the Loop in a Linked List
In order to break the Loop in a Linked List we need to set next pointer of one the nodes which are pointing to same node in the Linked List and also part of the Loop to NULL.
Remember that breaking the Loop should happen in such a way that all the nodes should remain in the Linked List (No nodes should be lost).
In above image, Node 7 is satisfying both condition and hence Node 7’s next pointer needs to be changed to NULL in order to break the loop.
Steps to break the Loop in a Linked List.
Is Loop Present in Linked List ?
First of all we need to find whether Linked List has any loops or not. We are going to use Floyd cycle’s detection algorithm to find out the loop in a Linked List.
Algorithm
- Define two pointers fast and slow, both pointing to head at the beginning
- Move Slow pointer to next node whereas Fast pointer should be jumped to next to next node. Basically Fast pointer should moved 2 places.
- Check whether Slow pointer and Fast pointer both are pointing to same address or not, if yes then there is a loop in Linked List.
- Repeat above 2 steps till we find the loop or we encountered the NULL.
- If NULL is encountered then there is no loop in the Linked List.
Let’s look into the sample code.
/* Below function will find the loop and return one of node
* present in the loop. NULL will be returned if loop is not
* present */
LinkedList* find_loop_in_linked_list (LinkedList* start)
{
LinkedList* slow = start;
LinkedList* fast = start;
while (fast)
{
slow = slow -> next;
if (!fast -> next)
break;
fast = fast -> next -> next;
if (slow == fast)
{
cout << "Loop found " << endl;
return slow;
}
}
cout << "Loop not found" << endl;
return NULL;
}
Find the Loop length
Once we found that loop exist in the Linked List, then we need to calculate the length of Loop in the Linked List. In the above picture, length of loop list = 4.
Let’s look into the sample code.
/* Loop Length will be returned */
int count_loop_length (LinkedList* loop_node)
{
LinkedList* temp = loop_node;
int count = 1;
while (temp -> next != loop_node)
{
temp = temp -> next;
count++;
}
cout << count << endl;
return count;
}
Find the starting node of the loop
In order to find the starting node of the loop, we will require two pointers and we need to traverse the linked list.
Algorithm
- Define two pointers fast and slow, both pointing to head at the begining.
- Move fast pointer to the length of loop. If loop length is 4 then fast pointer should be moved to 4th place.
- Both Fast and Slow pointer moved to next node.
- If Fast and Slow pointer both are pointing the same node then this is the starting node of the loop.
- Repeat above two steps.
Let’s look into the sample code.
/* Below function will return the starting node of the loop */
LinkedList* return_node_creating_loop (LinkedList* start, int loop_len)
{
LinkedList* fast = start;
LinkedList* slow = start;
int count = 0;
while (count != loop_len)
{
count++;
fast = fast -> next;
}
while (fast != slow)
{
fast = fast -> next;
slow = slow -> next;
}
return fast;
}
Alternate Method to find Starting node of the loop
In order to find the Starting Node in the loop, we need to use two pointers.
Algorithm
- Define fast pointer and point it to head of the Linked List.
- Define slow pointer and point it to the loop node (find while checking for loop in above function find_loop_in_linked_list)
- Move both pointer one place at a time.
- Check whether both fast and slow pointer are pointing at same node or not.
- If both fast and slow pointer are pointing to same node then that’s the starting node of the loop. else repeat above two steps.
Let’s look into the sample code.
LinkedList* alternate_method_to_find_starting_node (LinkedList* start, LinkedList* loop_node)
{
LinkedList* fast = start;
LinkedList* slow = loop_node;
while (fast != slow)
{
fast = fast -> next;
slow = slow -> next;
}
return fast;
}
Breaking the Loop in Linked List
In order to break the Loop in Linked List, we need to change next pointer of the previous node present in the loop to NULL. In the above image, Node 7’s next pointer should be set to NULL to break the loop.
Let’s look into the sample code.
void break_loop_in_linked_list (LinkedList* loop_node, LinkedList* node_at_loop)
{
LinkedList* temp = loop_node;
while (temp -> next != node_at_loop)
{
temp = temp -> next;
}
temp -> next = NULL;
}
Let’s define a function to combine all of the above functions
void find_loop_and_print_node (LinkedList* start)
{
LinkedList* loop_node = find_loop_in_linked_list (start);
if (loop_node)
{
cout << "There is a loop in passed Linked List, loop node: " << loop_node -> data << endl;
int len = count_loop_length (loop_node);
cout << "Length of loop: " << len << endl;
LinkedList* node_at_loop = return_node_creating_loop (start, len);
cout << "Node at which loop occurs: " << node_at_loop -> data << endl;
LinkedList* node_at_loop_2 = alternate_method_to_find_starting_node (start, loop_node);
cout << "Node at which loop occurs: " << node_at_loop_2 -> data << endl;
break_loop_in_linked_list (loop_node, node_at_loop);
print_linked_list (start);
return;
}
cout << "No Loop found in passed Linked List" << endl;
}
We can optimize above steps to make it faster, but we are keeping it simple and broken into small steps to emphasize on understanding the logic behind this problem.
Let’s define a main function to use above methods. Also we have defined a method to create a loop in the Linked List.
Few of the functions used below are explained in Linked List Insert operation, Linked List Delete Operation and Linked List Traverse and Search article . Refer those before moving ahead.
/* This function will create a loop in Linked List */
void insert_at_end_to_create_loop (LinkedList* start, int new_data, int search_data)
{
LinkedList* temp = start;
LinkedList* prev = start;
LinkedList* searched_node = NULL;
cout << "Inserting node " << new_data << endl;
while (temp)
{
if (temp -> data == search_data)
{
searched_node = temp;
}
prev = temp;
temp = temp -> next;
}
LinkedList* n = new LinkedList (new_data);
n -> next = searched_node;
prev -> next = n;
return;
}
int main ()
{
LinkedList* start = NULL;
print_linked_list (start);
insert_at_begining (&start, 3);
insert_after_certain_element (start, 5, 6);
insert_after_certain_element (start, 7, 5);
insert_after_certain_element (start, 9, 8);
insert_after_certain_element (start, 11, 10);
insert_after_certain_element (start, 16, 11);
insert_after_certain_element (start, 2, 9);
insert_after_certain_element (start, 15, 2);
print_linked_list (start);
/* We are creating a loop here, don't print linked list now */
insert_at_end_to_create_loop (start, 20, 9);
find_loop_and_print_node (start);
/* Loop is broken now */
print_linked_list (start);
cout << "Deleting Head Node " << endl;
delete_start_node (&start);
print_linked_list (start);
cout << "Deleting Node 11" << endl;
delete_searched_node (&start, 11);
print_linked_list (start);
cout << "Deleting all Nodes" << endl;
delete_all_node (&start);
print_linked_list (start);
}
Let’s analyze the output of this main function.
Linked list is null, nothing to print
Inserting node 5
Searched data not found, hence putting new node at the end
Inserting node 7
Inserting node 9
Searched data not found, hence putting new node at the end
Inserting node 11
Searched data not found, hence putting new node at the end
Inserting node 16
Inserting node 2
Inserting node 15
3 5 7 9 2 15 11 16
Inserting node 20
Loop found
There is a loop in passed Linked List, loop node: 11
6
Length of loop: 6
Node at which loop occurs: 9
Node at which loop occurs: 9
3 5 7 9 2 15 11 16 20
3 5 7 9 2 15 11 16 20
Deleting Head Node
5 7 9 2 15 11 16 20
Deleting Node 11
Node found, going to delete
5 7 9 2 15 16 20
Deleting all Nodes
Linked list is null, nothing to print
