How do you merge two sorted Linked Lists?

Difficulty: 3/10

linked list traversal, merge algorithm, pointer manipulation

Merging Sorted Linked Lists

Two sorted linked lists can be merged in linear time using two pointers. At each step, compare the current nodes and attach the smaller node to the result. A dummy node simplifies head handling and eliminates special cases.

javascript

1
Time complexity: O(m + n).
2
Auxiliary space: O(1) when existing nodes are reused.
3
The dummy node simplifies result-list construction.
4
The original lists can be reused if mutation is acceptable.
5
A new-node implementation would require additional memory.

Scenario Questions

0-2 years experience

Follow-up Questions