How to Solve Intersection of Linked List
Intersection of Linked List Introduction
Intersection of Linked List Introduction
The Intersection of linked list problem (also known as the Intersection of two linked list problem) asks us to return the node at which two linked lists intersect, if none then we return None. This problem requires us to consider the lengths of the given linked lists before using our pointers. Using the lengths we can adjust our starting positions accordingly. By using these two pointers effectively to traverse the lists we can find the point in which they intersect without comparing every node.
Intersection of Linked List Problem
Intersection of Linked List Problem
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return none.
Intersection of Linked List Solutions
Intersection of Linked List Solutions
We can solve this problem using two-pointers. We start by finding the lengths of the two linked lists and adjust the starting positions of the pointers accordingly. This step ensures that both pointers are at the same relative position from the end of their respective lists. Next, we traverse the linked lists simultaneously using the two pointers. We keep moving the pointers one node at a time until either they meet at an intersection point or both reach the end of their lists. By doing this, we can search for the intersection point without having to compare every node.
If the pointers meet, it means we have found the intersection point. We can return that node as the result. If the pointers reach the end of their lists without meeting, it let's us know that there is no intersection between the two linked lists. In this case, we return 'None' to signify the absence of an intersection.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
# Check if either list is empty
if not headA or not headB:
return None
# Get the lengths of both lists
lenA, lenB = 0, 0
nodeA, nodeB = headA, headB
while nodeA:
lenA += 1
nodeA = nodeA.next
while nodeB:
lenB += 1
nodeB = nodeB.next
# Move the longer list's head pointer to align the lengths
while lenA > lenB:
headA = headA.next
lenA -= 1
while lenB > lenA:
headB = headB.next
lenB -= 1
# Traverse both lists to find the intersection point
while headA != headB:
headA = headA.next
headB = headB.next
# Return the intersection node (or None if no intersection)
return headA
# Create linked lists for testing
# Intersection point at node with value 8
common = ListNode(8, ListNode(4, ListNode(5)))
headA = ListNode(4, ListNode(1, common))
headB = ListNode(5, ListNode(6, ListNode(1, common)))
# Test our solution
intersection = getIntersectionNode(headA, headB)
if intersection:
print("Intersection at node with value:", intersection.val)
else:
print("No intersection")
#Expected output: 81class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def getIntersectionNode(headA, headB):
7 # Check if either list is empty
8 if not headA or not headB:
9 return None
10
11 # Get the lengths of both lists
12 lenA, lenB = 0, 0
13 nodeA, nodeB = headA, headB
14 while nodeA:
15 lenA += 1
16 nodeA = nodeA.next
17 while nodeB:
18 lenB += 1
19 nodeB = nodeB.next
20
21 # Move the longer list's head pointer to align the lengths
22 while lenA > lenB:
23 headA = headA.next
24 lenA -= 1
25 while lenB > lenA:
26 headB = headB.next
27 lenB -= 1
28
29 # Traverse both lists to find the intersection point
30 while headA != headB:
31 headA = headA.next
32 headB = headB.next
33
34 # Return the intersection node (or None if no intersection)
35 return headA
36
37# Create linked lists for testing
38# Intersection point at node with value 8
39common = ListNode(8, ListNode(4, ListNode(5)))
40headA = ListNode(4, ListNode(1, common))
41headB = ListNode(5, ListNode(6, ListNode(1, common)))
42
43# Test our solution
44intersection = getIntersectionNode(headA, headB)
45if intersection:
46 print("Intersection at node with value:", intersection.val)
47else:
48 print("No intersection")
49
50#Expected output: 8Time/Space Complexity Analysis
- Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. We need to traverse both lists to calculate their lengths and then traverse them again simultaneously until we find the intersection point or reach the end. This means that the time complexity is linear with respect to the lengths of the lists.
- Space Complexity: O(1), as we only use a constant amount of extra space to store the two pointers and a few other variables.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
