94. Merge Two Sorted Linked Lists

Given two sorted singly linked lists (as n1 values, then n2 values), merge them into a single sorted list and print it.

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 single merged, sorted list, space-separated.

1 <= n1, n2 <= 10^5

This exact two-pointer merge is the foundational building block reused directly in 'Merge Sort on a Linked List' and 'Merge K Sorted Linked Lists' - mastering it here pays off immediately in both harder problems.

Combine two already-sorted linked lists into one single sorted linked list. Brute force: Copy both lists' values into one array, sort the whole array, and build a fresh linked list from it - this works but costs O((n1+n2) log(n1+n2)) for the sort, ignoring that both lists are ALREADY individually sorted. Optimised: Since both lists are already sorted, a two-pointer merge (directly relinking existing nodes rather than copying values) combines them in linear time - the exact same technique used to merge the 'merge' half of merge sort.

Read all n1 + n2 values from both lists into one combined array, sort that array from scratch, and build a new linked list from the sorted result. This produces the correct merged order but throws away the fact that both input lists are already individually sorted, paying full sorting cost unnecessarily. Time: O((n1+n2) log(n1+n2)) Space: O(n1+n2)

Use two pointers, one on each input list. Repeatedly compare the values at both pointers, allocate a brand-new node holding the smaller value, append it to the result list, and advance the pointer it came from; once one list is exhausted, copy the remainder of the other. This exploits the sorted property in a single linear pass, unlike the sort-based brute force, but it still allocates a full set of new nodes rather than reusing the existing ones. Time: O(n1+n2) Space: O(n1+n2)

Use the same two-pointer merge comparison, but instead of allocating new nodes, splice the existing nodes directly: repeatedly attach whichever of the two current nodes has the smaller value to the tail of the result by adjusting its next pointer, then advance that list's pointer, finally attaching whatever remains of the non-exhausted list. This produces the identical merged order as the previous approach while reusing the original nodes, so no new memory is allocated beyond a few pointers. Time: O(n1+n2) Space: O(1)

1. Use two pointers, one into each list, both starting at their respective heads. 2. At each step, compare the two pointers' current values and relink the SMALLER one onto the result, advancing that pointer. 3. Once one list is exhausted, attach the rest of the OTHER list directly (it's already sorted).

Time: O(n1 + n2) - each node from both lists is visited and relinked exactly once. Space: O(1) extra space if relinking existing nodes in place (versus O(n1+n2) if building an entirely new list).

n1 = 1 or n2 = 1 (minimum size), lists with overlapping or duplicate values, and lists each up to 10^5 for performance.

Be ready to implement this cleanly using a 'dummy head' node technique (a placeholder node before the real result starts) to avoid special-casing the very first node of the merged list - a small but widely-used trick.