700191. Intersection Sorted Linked Lists
Intersection of Two Sorted Linked Lists
Slug: intersection-of-two-sorted-linked-lists
Difficulty: Easy
Topic Tags: Linked List, Sorting, Data Structures, Algorithms
Company Tags: Amazon, Microsoft, D-E-Shaw, Zopper
Summary
The problem is to find the intersection of two sorted linked lists. This means we need to find the common elements present in both lists, and return them as a new sorted linked list.
We can approach this problem by maintaining pointers for both lists and comparing the current nodes until we find an element that is present in both lists. If such an element is found, it is added to the result list. We continue this process until we have processed all elements from both lists.
Detailed Explanation
To solve this problem, we can use two pointers approach. Initialize two pointers for both linked lists and move them one step at a time until they meet. If the nodes at the current positions of both pointers are equal, it means we have found an intersection node, so add it to our result list.
Here is the step-by-step breakdown:
- Create two pointers
p1andp2for both linked lists. - Move
p1one step at a time through the first linked list, and movep2one step at a time through the second linked list. - Compare the nodes pointed to by
p1andp2. If they are equal, it means we have found an intersection node, so add it to our result list. - Continue this process until either of the pointers reaches the end of its respective linked list.
- Return the result list.
Time complexity: O(m + n), where m and n are the lengths of the two linked lists. Space complexity: O(min(m, n)), as we need to store at most min(m, n) elements in our result list.
Optimized Solutions
Java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
p1 = p1 != null ? p1.next : headB;
p2 = p2 != null ? p2.next : headA;
}
return p1;
}