LinkedListProblem 11 of 36
Intersection of two Sorted Linked List
Intersection of Two Sorted Linked Lists
Problem Statement
Given two sorted linked lists, find and return a new sorted linked list that contains only the elements that are common to both input lists. The result should not contain duplicates.
Example
Input:
l1 = 1 -> 2 -> 3 -> 4 -> 6 -> null
l2 = 2 -> 4 -> 6 -> 8 -> null
Output: 2 -> 4 -> 6 -> null
Input:
l1 = 1 -> 2 -> 3 -> null
l2 = 4 -> 5 -> 6 -> null
Output: null (no common elements)
Input:
l1 = 1 -> 1 -> 2 -> 3 -> null
l2 = 1 -> 1 -> 3 -> null
Output: 1 -> 3 -> null (no duplicates in result)
Brute Force Approach (Nested Loops)
Intuition
For each element in the first list, search for it in the second list. If found and not already in result, add it to the result.
Algorithm
- For each node in l1
- Search for that value in l2
- If found and not duplicate, add to result
- Return result
Implementation
Complexity Analysis
- Time Complexity: O(m * n) - Nested iteration
- Space Complexity: O(min(m, n)) - Result list and set for duplicates
Optimal Approach (Two Pointer / Merge Technique)
Intuition
Since both lists are sorted, we can use a technique similar to merging sorted arrays. Use two pointers, one for each list:
- If values are equal, add to result and move both pointers
- If l1's value is smaller, move l1's pointer
- If l2's value is smaller, move l2's pointer
Algorithm
- Initialize two pointers at the heads of both lists
- While both pointers are not null:
- If values match, add to result (skip duplicates), advance both
- If l1->val < l2->val, advance l1
- Else advance l2
- Return result
Visualization
l1: 1 -> 2 -> 3 -> 4 -> 6
↑
p1
l2: 2 -> 4 -> 6 -> 8
↑
p2
Step 1: 1 < 2, move p1
Step 2: 2 == 2, add 2, move both
Step 3: 3 < 4, move p1
Step 4: 4 == 4, add 4, move both
Step 5: 6 == 6, add 6, move both
Step 6: p1 is null, stop
Result: 2 -> 4 -> 6
Implementation
Complexity Analysis
- Time Complexity: O(m + n) - Single pass through both lists
- Space Complexity: O(min(m, n)) - Result list only
Variant: Find Union of Two Sorted Lists
Find all unique elements from both lists (union instead of intersection):
Comparison: Intersection vs Union
| Operation | Time | Space | Description | |-----------|------|-------|-------------| | Intersection | O(m+n) | O(min(m,n)) | Common elements only | | Union | O(m+n) | O(m+n) | All unique elements |
Key Takeaways
- Sorted property enables the efficient two-pointer approach
- This is similar to merging sorted arrays but with different logic
- The technique is also used in merge sort's merge step
- Handle duplicates carefully - check before adding to result
- Time complexity improves from O(m*n) to O(m+n) using the sorted property
- The same technique applies to arrays - it's a fundamental pattern