Introduction

Merge Two Sorted Lists means combining two sorted linked lists into one sorted linked list.

The task is to:

  • compare nodes from both lists
  • attach smaller node first
  • maintain sorted order

Example:

Input:List1:
1 -> 3 -> 5

List2:
2 -> 4 -> 6

Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Explanation:

Smaller node is selected at every step.Final linked list remains sorted.

This problem is one of the most important applications of:

Pointer Manipulation

Constraints

0 <= Number of Nodes <= 10^5
-10^9 <= Node Value <= 10^9

Approach 1 : Brute Force (Using Array)

Explanations:

Explanation:

The idea is:

  • store both linked lists in array
  • sort all elements
  • rebuild linked list

Steps:

  1. Traverse first list.
  2. Traverse second list.
  3. Store all values.
  4. Sort array.
  5. Create merged list.

This approach works but:

  • uses extra memory

So pointer merging is preferred.

Dry Run

Input:1 -> 3 -> 5
2 -> 4 -> 6

Array:
[1,3,5,2,4,6]

Sorted:
[1,2,3,4,5,6]

Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Practice :

Complexity Analysis :

Time Complexity:- O(n log n)
Explanation :
Sorting array takes extra time.

Space Complexity:- O(n)
Explanation :
Extra array is used.

Approach 2 : Optimal Solution(Using Pointer Merging)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • compare nodes from both lists
  • attach smaller node
  • move corresponding pointer

This performs merging in-place.

Dry Run

Input:1 -> 3 -> 5
2 -> 4 -> 6

Compare:
1 and 2

Attach:
1

Compare:
3 and 2

Attach:
2

Continue process.

Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Practice :

Complexity Analysis :

Time Complexity:- O(n)
Explanation :
Each node is visited once.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Why This Problem is Important

This problem builds the foundation for:

  • Linked List merging
  • Pointer manipulation
  • Sorted data handling
  • Merge Sort logic
  • In-place algorithms

Real-World Applications

Merge operations are used in:

  • Merge sort algorithm
  • Database merging
  • Data synchronization
  • Streaming systems
  • File processing systems

Common Beginner Mistakes

  • Incorrect pointer movement
  • Forgetting remaining nodes
  • Breaking linked structure
  • Infinite loops
  • Wrong comparison logic

Interview Tip

Interviewers often expect:

  • clean pointer manipulation
  • efficient merging logic
  • O(1) space optimization
  • sorted traversal handling

Always explain:

  • how smaller node is selected
  • how remaining nodes are attached

Related Questions

  • Merge K Sorted Lists
  • Reverse Linked List
  • Linked List Cycle
  • Sort Linked List
  • Middle of Linked List

Final Takeaway

The Merge Two Sorted Lists problem is one of the most important linked list interview problems.

It teaches:

  • linked list merging
  • sorted traversal
  • pointer manipulation
  • in-place algorithms

Understanding this problem builds a strong foundation for:

  •  merge sort algorithms
  • advanced linked list problems
  • interview-level data structure questions.