Driver code
Let's check out the main function before moving to each approach. We initialize two linked lists in the main function: list1 and list2 with the common nodes. The value of the intersection node is obtained from the function intersectionPoint().
Main function:
public class Main {
public static void main(String[] args) {
// linked list 1
ListNode list1 = new ListNode(4);
list1.next = new ListNode(1);
list1.next.next = new ListNode(8);
list1.next.next.next = new ListNode(4);
list1.next.next.next.next = new ListNode(5);
System.out.print("First Linked List is ");
printList(list1);
// linked list 2
ListNode list2 = new ListNode(5);
list2.next = new ListNode(6);
list2.next.next = new ListNode(1);
list2.next.next.next = list1.next.next;
System.out.print("Second Linked List is ");
printList(list2);
int result = intersectionPoint(list1, list2);
System.out.println("The intersection point of two linked lists: " + result);
}
}
Let's also check out the ListNode class and printList() function, repeatedly used in the program.
Also read  Merge sort in linked list
Class ListNode:
// class representing the node in the linked list
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
Function printList():
// function to print linked list
private static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
Also see, Rabin Karp Algorithm
The intersection point of two linked lists: Using Loops
In this approach, nested loops are used. The outer loop selects a node from the first linked list, and the inner loop selects a node from the second linked list. When both the linked lists reach the same node, return the value of the node.
Steps:
 Initialize an outer loop for the first linked list.
 Initialize the inner loop for the second linked list.
 Traverse the linked lists till the intersecting node is met.
 Return the value of the intersecting node.
Code:
public class Main {
// function to find the intersection of two linked lists
private static int intersectionPoint(ListNode list1, ListNode list2) {
ListNode firstTemp = list1;
while (firstTemp != null) {
ListNode temp = list2;
while (temp != null) {
// if both linked lists points to the same node
if (firstTemp == temp) {
return firstTemp .val;
}
temp = temp.next;
}
firstTemp = firstTemp .next;
}
// if there is no intersecting node
return 1;
}
}
Output
First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8
Complexity Analysis:
 Time Complexity: O(m * n) as there is a nested loop.
 Space Complexity: O(1)
m: number of nodes in the first linked list
n: number of nodes in the second linked list
The intersection point of two linked lists: Using Hashing
In this approach, the nodes of the first linked list are stored in a HashSet. Then the nodes in the second linked list are stored in the HashSet till the intersecting point of two Linked Lists is met.
Steps:
 Create an empty HashSet.
 Traverse the first linked list and store all the nodes.
 Traverse the second linked list and store the nodes till the intersecting node is met.

Return the value of the intersecting node.
Code:
import java.util.HashSet;
public class Main {
// function to find the intersection of two linked lists
private static int intersectionPoint(ListNode list1, ListNode list2) {
// define hashset
HashSet<ListNode> hashset = new HashSet<ListNode>();
// add all the nodes in the hashset
ListNode firstTemp = list1;
while(firstTemp != null) {
hashset.add(firstTemp );
firstTemp = firstTemp .next;
}
// check if the intersecting node is present
ListNode secondTemp = list2;
while(secondTemp != null) {
if(hashset.contains(secondTemp ))
return secondTemp.val;
hashset.add(secondTemp );
list2 = secondTemp.next;
}
// if there is no intersecting node
return 1;
}
}
Output
First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8
Complexity Analysis:
 Time Complexity: O(m + n) as the linked lists are traversed once.
 Space Complexity: O(m + n) as extra space is required for the HashSet.
The intersection point of two linked lists: Using the difference of node counts
In this approach, the bigger node is traversed until both the linked lists have the same size. Then both the linked lists are traversed at the same speed till the intersection point is encountered.
Steps:
 Find the size of linked lists.
 Calculate the difference (d) in the sizes of the linked list.
 Swap the linked list to make the first linked list larger (if required).
 Traverse the bigger list till d.

Both the linked lists have equal nodes from the intersection point, and then traverse until the intersection point is reached.
Code:
public class Main {
// function to get the size of the linked lists
private static int getSize(ListNode list) {
int size = 0;
while (list != null) {
size++;
list = list.next;
}
return size;
}
// function to find the intersection of two linked lists
private static int intersectionPoint(ListNode list1, ListNode list2) {
int size1 = getSize(list1), size2 = getSize(list2);
int sizeDifference = Math.abs(size1  size2);
ListNode tempList1 = list1, tempList2 = list2;
// swap to make the first linked list larger in size
if (size2 > size1) {
ListNode temp = tempList2;
tempList2 = tempList1;
tempList1 = temp;
}
// traverse the bigger linked lists till both the linked lists have same number
// of nodes
for (int i = 0; i < sizeDifference; i++) {
tempList1 = tempList1.next;
}
// check if the linked lists have a common node
while (tempList1 != null && tempList2 != null) {
if (tempList1 == tempList2) {
return tempList1.val;
}
tempList1 = tempList1.next;
tempList2 = tempList2.next;
}
// if there is no intersecting node
return 1;
}
}
Output
First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8
Complexity Analysis:
 Time Complexity: O(m + n)
 Space Complexity: O(1)
The intersection point of two linked lists: Using Floyd's Cycle Detection Algorithm
In this approach, the first linked list is converted to a circular linked list by connecting the tail to its head. Then two pointers are considered: one pointing to the head node and the other pointing to the kth (total number of nodes in the loop) node from the head. These pointers are then moved with the same speeds to get the intersection point of two linked lists.
Refer to the blog Floyd's Cycle Detection Algorithm for a better understanding.
Steps:
 Convert the first linked list into a circular linked list.
 Detect if a cycle is present.
 Set two pointers: one at the head of the loop and the other at the kth node.
 Simultaneously move the list and current pointers at the same speed until they meet.
 Return the current value, which is the value of the intersecting node.
 Remove the cycle from the linked list.
Code:
public class Main {
// function to find node
private static ListNode findNode(ListNode slow, ListNode list) {
// count of nodes in the loop
int count = 1;
for (ListNode pointer = slow; pointer.next != slow; pointer = pointer.next) {
count++;
}
// pointer at a distance of count from the start of the loop
ListNode current = list;
for (int i = 0; i < count; i++) {
current = current.next;
}
// simultaneously move the list and current pointers at the same speed until they meet
while (current != list) {
current = current.next;
list = list.next;
}
// returns the starting node of the loop
return current;
}
// function to detect the cycle
private static ListNode identifyCycle(ListNode list) {
ListNode slow = list, fast = list;
while (fast != null && fast.next != null) {
// move slow by one pointer
slow = slow.next;
// move fast by two pointers
fast = fast.next.next;
// if pointers meet at any node, the linked list contains a cycle
if (slow == fast) {
return slow;
}
}
// cycle is not present in the linked list
return null;
}
// function to find the intersection of two linked lists
private static int intersectionPoint(ListNode list1, ListNode list2) {
ListNode previous = null, current = list1;
// traverse the list1 and get the pointer to the last nod
while (current != null) {
previous = current;
current = current.next;
}
// create a cycle in the list1
if (previous != null) {
previous.next = list1;
}
// pointer to the loop node
ListNode slow = identifyCycle(list2);
// find the intersection node
ListNode intersectionNode = null;
if (slow != null) {
intersectionNode = findNode(slow, list2);
}
// remove cycle in the list1
if (previous != null) {
previous.next = null;
}
int result = intersectionNode == null ? 1 : intersectionNode.val;
return result;
}
}
Output
First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8
Complexity Analysis:
 Time Complexity: O(m + n)
 Space Complexity: O(1)
The intersection point of two linked lists: Twopointer Approach
In this approach, two pointers pointing at the head node of the linked list are taken. When the pointer reaches the end of the linked list, it is reassigned to the other list. After both the pointers are reassigned, they will be equidistant from the intersection point. Finally, the intersection point of two linked lists is obtained when the pointers become equal and are not null.
Steps:
 Initialize two pointers head1 and head2, at the head of list1 and list2, respectively.
 Traverse through the linked lists
 When head1 reaches the end of a list, then assign it to list2.
 When head2 reaches the end of a list, then assign it to list1.
 When both of them are reassigned, they will be equidistant from the intersection point.
 The point where head1 equals head2 and both are not null is the intersection point of two linked lists.
Code:
public class Main {
// function to find the intersection of two linked lists
private static int intersectionPoint(ListNode list1, ListNode list2) {
ListNode head1 = list1;
ListNode head2 = list2;
// no intersection point if any one of the head is null
if (head1 == null  head2 == null) {
return 1;
}
// traverse through the linked lists until intersection node is reached
while (head1 != head2) {
head1 = head1.next;
head2 = head2.next;
// intersection point if both the nodes are same and are not null
if (head1 == head2) {
// no intersection node
if(head1 == null)
return 1;
else
return head1.val;
}
// reassign it to the list2 when head1 reaches the end
if (head1 == null) {
head1 = list2;
}
// redirect it to the list1 when head1 reaches the end
if (head2 == null) {
head2 = list1;
}
}
return 1;
}
}
Output
First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8
Complexity Analysis:
 Time Complexity: O(m + n)
 Space Complexity: O(1)
Frequently Asked Questions
What is Floyd's cycle detection algorithm?
Floyd's Cycle detection algorithm or Hair Tortoise algorithm detects a cycle in a linked list. It uses two pointers moving through the sequence at different speeds.
How to link two linked lists together?
Two linked lists can be linked together by attaching the head of another list to the tail of the current linked list.
What is the time and space complexity of Floyd's cycle detection algorithm?
The time complexity is O(N), and the space complexity is O(1) in Floyd's cycle detection algorithm. Here, "N" represents the number of nodes in the linked list.
What is a linked list?
A Linked List is a linear data structure where the elements called nodes are stored at noncontiguous memory locations.
Explain the approach to convert a singly linked list to a circular linked list?
Traverse the singly linked list, and when the last node is reached, attach it to the head node.
Conclusion
This blog covered the various methods to find the intersection point of two linked lists. The methods discussed here are using loops, hashing, the difference of node count, the Floyd cycle detection algorithm, and the twopointer approach.
Now that you know how to approach a problem in Linked List check out some of the other articles based on them, such as Advantages Of Linked List, Linked List in Java, Dynamic Memory Allocation in C on our Coding Ninjas Studio Platform!
Don't stop here. Check out our Data Structures and Algorithmsguided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach