Intersection of two sorted linked lists (by value)
Problem
Given two sorted linked lists, return a new list of the values present in both, in sorted order.
Example 1
Input: 1 → 2 → 3 → 4 → 6 and 2 → 4 → 6 → 8 Output: 2 → 4 → 6
Also asked as: Intersection of two Sorted Linked List
Test cases
Case 1
Input: [1,2,3,4,6], [2,4,6,8] Expected: [2,4,6]
Case 2
Input: [1,2,3], [1,2,3] Expected: [1,2,3]
Case 3
Input: [1,2], [3,4] Expected: []
Case 4
Input: [], [1] Expected: []
View solutionHide solution1 approach
1. Merge-style two pointers
Time O(n + m)Space O(1) besides output
Advance the smaller head; equal values go to the result list.
function sortedIntersection(a, b) { const dummy = { val: 0, next: null }; let tail = dummy; while (a && b) { if (a.val < b.val) a = a.next; else if (a.val > b.val) b = b.next; else { tail.next = { val: a.val, next: null }; tail = tail.next; a = a.next; b = b.next; } } return dummy.next;}