BL
U

64. Merge Two Sorted Linked Lists

Easy

Problem Description

Merge two sorted singly linked lists into a single sorted linked list.

Input Format

  • •Line 1: Two space-separated integers NN and MM.
  • •Line 2: NN sorted integers.
  • •Line 3: MM sorted integers.

Output Format

Print N+MN+M sorted integers space-separated.

Example 1:
Input:
3 3
1 2 4
1 3 4
Output:
1 1 2 3 4 4
Explanation: Merged sorted sequence.
Example 2:
Input:
2 0
5 10
Output:
5 10
Explanation: Second list empty.
Example 3:
Input:
1 2
2
1 3
Output:
1 2 3
Explanation: Lists merged into 1 2 3.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online