Similar Problems
Similar Problems not available
Intersection Of Two Linked Lists  Leetcode Solution
Companies:
LeetCode: Intersection Of Two Linked Lists Leetcode Solution
Difficulty: Easy
Topics: hashtable linkedlist twopointers
Problem Statement:
Write a program to find the node at which the intersection of two singly linked lists begins.
Example:
Input:
LinkedList1: 4 > 1 > 8 > 4 > 5 LinkedList2: 5 > 0 > 1 > 8 > 4 > 5
Output:
Node at which intersection of two linked lists begins: 8
Explanation:
In the input, the linked lists intersect at node 8.
Solution:
Approach:
The problem can be solved using a 2pointer approach. We can iterate over both the linked lists at the same time using two pointers. When one of the pointers reach the end of the linked list, we set that pointer to the head of the other linked list. So, the two pointers will always be the same length away from the intersection point of the linked lists. When the two pointers meet at the intersection node, we return that node.
Algorithm:

Traverse through the first linked list and compute the length of the list, store it in a variable called len1.

Traverse through the second linked list and compute the length of the list, store it in a variable called len2.

Compute the difference in lengths of the two linked lists. If len1 is greater than len2, set p1 to point to the head of the first linked list and move it forward by (len1  len2) nodes. If len2 is greater than len1, set p2 to point to the head of the second linked list and move it forward by (len2  len1) nodes.

Traverse through both linked lists at the same time using two pointers, p1 and p2. Stop when p1 and p2 point to the same node. Return the node.
Pseudo Code:
 Compute the length of the first linked list.
 Compute the length of the second linked list.
 Compute the difference in lengths of the two linked lists.
 Set p1 to the head of the first linked list and move it forward by (len1  len2) nodes; set p2 to the head of the second linked list and move it forward by (len2  len1) nodes.
 Traverse through both linked lists at the same time using the two pointers p1 and p2.
 Stop when p1 and p2 point to the same node.
 Return the node.
Implementation:
def getIntersectionNode(headA: ListNode, headB: ListNode) > ListNode: lenA, lenB = 0, 0 p1, p2 = headA, headB
# Traverse through the first linked list and compute the length of the list
while p1:
lenA += 1
p1 = p1.next
# Traverse through the second linked list and compute the length of the list
while p2:
lenB += 1
p2 = p2.next
# Compute the difference in lengths of the two linked lists
diff = abs(lenA  lenB)
# Set p1 to the head of the first linked list
p1 = headA
# Move p1 forward by (lenA  lenB) nodes
if lenA > lenB:
for i in range(diff):
p1 = p1.next
else:
p2 = headB
for i in range(diff):
p2 = p2.next
# Traverse through both linked lists at the same time using the two pointers p1 and p2
while p1 and p2:
# Stop when p1 and p2 point to the same node
if p1 == p2:
return p1
p1 = p1.next
p2 = p2.next
return None
Time complexity: O(m + n) where m and n are the lengths of the two linked lists. Space complexity: O(1).
Intersection Of Two Linked Lists Solution Code
1