🔗 Merge Two Sorted Doubly Linked Lists

Visualize merging two sorted doubly linked lists into one sorted list!

🎯 Problem: Merge Two Sorted Doubly Linked Lists

Hi! I'm Teju 👋 We are given two sorted doubly linked lists and need to merge them into a single sorted doubly linked list.

The merge should preserve the sorted order and maintain proper prev/next links.

Input:

• N1 → values of List 1
• N2 → values of List 2

Output: One merged sorted doubly linked list

Example:
List 1: 1 ↔ 3 ↔ 5
List 2: 2 ↔ 4 ↔ 6
→ Merged: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6

⚙️ Merge Algorithm

We use a method similar to merge step in merge sort: compare heads of both lists and always pick the smaller one.

  1. Create a dummy node as starting point
  2. While both lists are non-empty:
    • If List1 head ≤ List2 head → attach List1 head to result, move List1 forward
    • Else → attach List2 head to result, move List2 forward
  3. Attach remaining nodes of the non-empty list
  4. Return the list starting after dummy node

🎮 Interactive Demo

Enter details for both lists and click "Build Lists"...

List 1
null ↔ Empty
List 2
null ↔ Empty
Merged Result
null ↔ Empty

📋 Final Merged List