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;
}
Intersection Point of Two Linked List
This scenario might happen due to some programming error in case where two or more Linked List are present in the System. It might be possible that due to this error, one of the Linked List is actually pointing to certain element of Linked List 2 and thus kind of creating an intersection. In this article, we will find out the intersection point of such lists.
Let’s look into the below figure to make it more clear.
There are multiple methods to find out the intersection point. Here we are going to talk about the simplest yet one of the fastest method.
Algorithm to find intersection point of two Linked List
- Calculate the length of Linked List 1 (len_1)
- Calculate the length of Linked List 2 (len_2)
- If len_1 > len_2 then traverse Linked List 1 to (len_1 – len_2)th node else traverse Linked List 2 to (len_2 – len_1)th node.
- Check whether both list pointing to same node (address comparison).
- If both list addresses are different then move both pointer to next node present in their list respectively.
- Repeat above 2 steps until intersection point is found or end of list is found.
Let’s look into the sample code.
Few of the functions used below are explained in
- Linked List Insert operation
- Linked List Delete Operation
- Linked List Traverse and Search article
- Linked List length calculation
- Linked List swap k node
Refer those before moving ahead.
LinkedList* find_intersection_node (LinkedList* list1, LinkedList* list2)
{
int len_1 = length_of_linked_list_using_recursion (list1);
int len_2 = length_of_linked_list_using_recursion (list2);
LinkedList* temp_l1 = list1;
LinkedList* temp_l2 = list2;
if (len_1 > len_2)
{
temp_l1 = return_kth_node (list1, (len_1 - len_2));
}
else
{
temp_l2 = return_kth_node (list2, (len_2 - len_1));
}
while (temp_l1 && temp_l2)
{
if (temp_l1 == temp_l2)
{
cout << "Found Intersection Node: " << temp_l2 -> data << endl;
return temp_l2;
}
temp_l2 = temp_l2 -> next;
temp_l1 = temp_l1 -> next;
}
return NULL;
}
Let’s define a main function to use above methods.
/* This function will point last node of list1 Linked List to
* list2 Linked List kth place node
*/
void merge_two_lists(LinkedList* list1, LinkedList* list2, int k)
{
LinkedList* end_list1 = list1;
/* Finding last node of list1 */
while (end_list1 -> next)
{
end_list1 = end_list1 -> next;
}
/* Finding kth node of list2 */
int count = 0;
LinkedList* k_node_list2 = list2;
while (k_node_list2 -> next && count < k)
{
count++;
k_node_list2 = k_node_list2 -> next;
}
end_list1 -> next = k_node_list2;
}
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);
insert_after_certain_element (start, 21, 2);
insert_after_certain_element (start, 23, 3);
insert_after_certain_element (start, 35, 5);
insert_after_certain_element (start, 1, 11);
print_linked_list (start);
LinkedList* start_2 = NULL;
print_linked_list (start_2);
insert_at_begining (&start_2, 30);
insert_after_certain_element (start_2, 50, 60);
insert_after_certain_element (start_2, 70, 50);
insert_after_certain_element (start_2, 90, 80);
insert_after_certain_element (start_2, 110, 100);
insert_after_certain_element (start_2, 160, 110);
insert_after_certain_element (start_2, 20, 90);
insert_after_certain_element (start_2, 150, 20);
insert_after_certain_element (start_2, 210, 20);
insert_after_certain_element (start_2, 230, 30);
insert_after_certain_element (start_2, 350, 50);
insert_after_certain_element (start_2, 10, 110);
print_linked_list (start_2);
merge_two_lists (start, start_2, 5);
cout << "After Merging Lists are" << endl;
print_linked_list (start);
print_linked_list (start_2);
LinkedList* intersection_point = find_intersection_node (start, start_2);
delete_all_node (&start);
delete_all_node (&start_2);
}
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
Inserting node 21
Inserting node 23
Inserting node 35
Inserting node 1
3 23 5 35 7 9 2 21 15 11 1 16
Linked list is null, nothing to print
Inserting node 50
Searched data not found, hence putting new node at the end
Inserting node 70
Inserting node 90
Searched data not found, hence putting new node at the end
Inserting node 110
Searched data not found, hence putting new node at the end
Inserting node 160
Inserting node 20
Inserting node 150
Inserting node 210
Inserting node 230
Inserting node 350
Inserting node 10
30 230 50 350 70 90 20 210 150 110 10 160
After Merging Lists are
3 23 5 35 7 9 2 21 15 11 1 16 90 20 210 150 110 10 160
30 230 50 350 70 90 20 210 150 110 10 160
Found Intersection Node: 90
