How do you merge two sorted Linked Lists?

0-2 years experience

1. 1We have two sorted singly linked lists of user IDs. Write a function that returns a new list merging them in order. How would you approach it?
2. 2If one of the input lists is empty, what should your function return and why?
3. 3How does your merge handle duplicate values that appear in both lists?

2-5 years experience

1. 1Our service concatenates two sorted event streams stored as linked lists before sending downstream, but after a recent change the merged stream sometimes has out‑of‑order events. Walk me through how you'd debug the merge implementation.
2. 2We need to merge the two lists in place without allocating new nodes to reduce memory pressure. Explain the trade‑offs and sketch your implementation.
3. 3Suppose the lists can be very long and a recursive solution risks stack overflow. How would you adapt your code for production use?

5-8 years experience

1. 1Our microservice processes millions of sorted linked lists and merges them pairwise. Discuss the performance implications of an iterative versus recursive merge and how you'd scale this component.
2. 2The current merge function mutates the input lists, causing bugs elsewhere in the system. How would you redesign the API to be safer while still using O(1) extra space?
3. 3If the linked lists reside on different machines and you must merge them with minimal network hops, what architectural changes would you consider?

8+ years experience

1. 1Our platform is moving from in‑memory linked list structures to a persisted graph database. How would you migrate the existing merge‑two‑sorted‑lists functionality while ensuring data consistency and minimal downtime?
2. 2Multiple teams rely on a shared library that provides a merge function, but requirements have diverged (some need stable ordering, others need deduplication). How would you evolve the library's design to accommodate these needs without breaking existing contracts?
3. 3We anticipate future data types beyond integers, such as custom objects with complex comparators. How would you design a generic, extensible merge utility that can be used across services and languages?