Intersection of two sorted linked lists (by value)

Easy

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}