248. Intersection of Two Sorted Linked Lists

Given two sorted singly linked lists (as n1 values, then n2 values), print the values that appear in both lists, in sorted order. If a value repeats in both lists, include it as many times as it validly pairs up between the two lists. If there is no common value, print -1.

Input: The first line contains an integer n1 followed by a line of n1 sorted integers for the first list. The next line contains an integer n2 followed by a line of n2 sorted integers for the second list. Output: Print the values common to both lists, in sorted order, space-separated; print -1 if there is no common value.

1 <= n1, n2 <= 10^5

This is the linked-list version of the classic 'intersection of two sorted arrays' two-pointer technique - recognizing the shared underlying pattern across both data structures is a valuable, transferable skill.

Given two sorted linked lists, find the values that appear in both, in sorted order. Brute force: For every value in the first list, scan the entire second list directly checking for a match - this costs O(n1 * n2), unnecessary given that both lists are already sorted. Optimised: Since both lists are sorted, a two-pointer walk (the exact same merge-style technique used for merging two sorted lists) finds every common value in a single combined linear pass, advancing only the pointer that's behind at each step.

Since both lists are already sorted, walk two pointers through them simultaneously, much like the merge step of merge sort: compare the current values of both pointers - if they're equal, print the value and advance both pointers; if list one's current value is smaller, advance only list one's pointer; otherwise advance only list two's pointer. This exploits the sorted property to find every intersection in a single synchronized pass with no auxiliary counting structure needed at all. Time: O(n1 + n2) Space: O(1)

For every node in the first list, scan through the entire second list looking for a node with an equal value, and print it as part of the intersection whenever a match is found (being careful, in the repeated-value case, to only match each list node once so pairing stays consistent). This directly checks the definition of intersection by brute comparison, but re-scanning all of list two for every node of list one makes it quadratic in the combined list lengths. Time: O(n1 * n2) Space: O(1)

Traverse the second list once, building a hash map (or multiset) that counts how many times each value occurs. Then traverse the first list once, and for every value that has a remaining positive count in the map, output it and decrement that count (so repeated values are matched up correctly without over-counting). This replaces the expensive repeated re-scans of the second list with a single counting pass plus a single lookup pass, at the cost of memory to store the counts. Time: O(n1 + n2) Space: O(n2)

1. Walk both lists together with two pointers, since both are already sorted. 2. Advance whichever pointer is BEHIND (pointing to the smaller value). 3. When both point to EQUAL values, that's a match - record it and advance BOTH pointers.

Time: O(n1 + n2) - a single combined pass through both lists. Space: O(1) extra space beyond the pointers and the output list.

no common values at all (print -1), repeated values in both lists requiring multiple matched pairs, and n1, n2 each up to 10^5 for performance.

Be precise about the exact output convention for repeated shared values (include as many times as they validly pair up) and the -1 convention for no matches at all - both small but easy-to-miss details in this problem's exact statement.