Lesson 4 � Intermediate

Merge Two Sorted Lists

Two sorted lists ko merge karna � ye problem itni important hai ki ispe based poora merge sort algorithm banta hai. Dummy node technique seekhni hai jo bahut si linked list problems mein kaam aati hai. Chalo step by step samajhte hain.

? 18 min✓ Intermediate✓ Linked Lists Basics

Problem Statement

WHAT

Do sorted linked lists diye gaye hain � tumhe unhe merge karke ek naya sorted linked list banana hai. Dono lists already sorted hain ascending order mein. Merged list bhi sorted honi chahiye.

WHEN

Merge sort algorithm ka last step hai � do sorted halves ko merge karna. External sorting, k-way merge, sorted arrays merge karna � sab mein ye pattern use hota hai. Interview mein ye ek classic problem hai.

WHERE

Merge sort implementation, sorted array/list merging, database merge operations, k-way merge in distributed systems, playlist merging (sorted by time).

Why important? Merge sorted lists merge sort ka heart hai. Agar ye samajh liya toh merge sort ka linked list version automatically aa jaayega. Plus � dummy node technique jo yahan seekhoge wo 10+ linked list problems mein kaam aayegi.

# Example
# List 1: 1 ? 3 ? 5 ✓ None
# List 2: 2 ? 4 ? 6 ✓ None
# 
# Merged: 1 ? 2 ? 3 ? 4 ? 5 ? 6 ✓ None
#
# Compare 1 and 2 ✓ pick 1
# Compare 3 and 2 ✓ pick 2
# Compare 3 and 4 ✓ pick 3
# Compare 5 and 4 ✓ pick 4
# Compare 5 and 6 ✓ pick 5
# List 1 khatam ✓ pick 6 from List 2

Dummy Node Technique

Dummy node ek dummy/headless node hota hai jo simplifies karta hai linked list operations ko. Isse tumhe special cases handle nahi karne padte � jaise merged list ka head kaise set karein.

# Dummy node technique � sabse clean approach
class Node:
 def __init__(self, data):
 self.data = data
 self.next = None

def merge_two_sorted(l1, l2):
 dummy = Node(0) # Dummy node � result list ka starting point
 curr = dummy # Current pointer
 
 while l1 is not None and l2 is not None:
 if l1.data <= l2.data:
 curr.next = l1
 l1 = l1.next
 else:
 curr.next = l2
 l2 = l2.next
 curr = curr.next
 
 # Agar ek list khatam ho gayi toh baaki attach karo
 curr.next = l1 if l1 is not None else l2
 
 return dummy.next # Dummy ke next se actual head hai

Dummy Node kyun use karte hain? Without dummy node, tumhe har baar check karna padta hai ki merged list empty hai ya nahi � head kaise set karein✓ Dummy node se ye problem khatam. Dumy node hamesha merged list ka pehla node hai, aur dummy.next actual head hai. Clean code, fewer bugs.

Step-by-Step Merge Process

Chalo dekhte hain kaise merge hota hai. Har step mein compare karo, chhota wala pick karo, aur aage badho.

# Detailed step-by-step merge
# l1: 1 ? 3 ? 5 ? 7
# l2: 2 ? 4 ? 6 ? 8
#
# Step 1: Compare 1 and 2 ✓ pick 1
# dummy ? 1
# l1 moves to 3
#
# Step 2: Compare 3 and 2 ✓ pick 2
# dummy ? 1 ? 2
# l2 moves to 4
#
# Step 3: Compare 3 and 4 ✓ pick 3
# dummy ? 1 ? 2 ? 3
# l1 moves to 5
#
# Step 4: Compare 5 and 4 ✓ pick 4
# dummy ? 1 ? 2 ? 3 ? 4
# l2 moves to 6
#
# Step 5: Compare 5 and 6 ✓ pick 5
# dummy ? 1 ? 2 ? 3 ? 4 ? 5
# l1 moves to 7
#
# Step 6: Compare 7 and 6 ✓ pick 6
# dummy ? 1 ? 2 ? 3 ? 4 ? 5 ? 6
# l2 moves to 8
#
# Step 7: Compare 7 and 8 ✓ pick 7
# dummy ? 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7
# l1 moves to None
#
# l1 is None ✓ attach remaining l2 (8)
# Final: 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8

Edge Cases:
- Ek list empty hai ✓ baaki list return karo
- Dono lists empty hain ✓ None return karo
- Lists ka size alag hai ✓ chhoti list khatam hone pe baaki attach karo
- Duplicate values hain ? l1.data <= l2.data se✓ maintain hoti hai

Merge Sort se Connection

Merge sorted lists merge sort ka fundamental building block hai. Linked list mein merge sort arrays se zyada efficient hota hai kyunki space O(1) hota hai (dummy node exception hai but still better than array merge).

# Merge Sort on Linked List � full implementation
def merge_sort(head):
 # Base case: 0 ya 1 node
 if head is None or head.next is None:
 return head
 
 # Middle node dhundho (slow-fast technique)
 slow = head
 fast = head.next
 while fast and fast.next:
 slow = slow.next
 fast = fast.next.next
 
 # Do halves mein todo
 mid = slow.next
 slow.next = None # First half ka end
 
 # Recursively sort both halves
 left = merge_sort(head)
 right = merge_sort(mid)
 
 # Merge karo
 return merge_two_sorted(left, right)

# Time: O(n log n)
# Space: O(log n) recursion stack � arrays mein O(n) hota hai

Linked List vs Array Merge Sort:
Array: O(n) extra space for merging
Linked List: O(1) extra space (dummy node is temporary)
Array: Random access O(1) � middle finding easy
Linked List: No random access � slow-fast for middle, but overall space better

Try it: code khud likho

Exercise

Question: [1,3,5] aur [2,4,6] ko merge karo. Merged sorted list likho.

Question: Agar l1 = None aur l2 = [1,2,3] hai toh merged list kya hogi?

Common mistakes

Not returning dummy.next: Dummy node actual list ka part nahi hai. Hamesha return dummy.next karo, return dummy nahi.
Forgetting remaining elements: Loop khatam hone ke baad jo list bachi hai uska next attach karna bhool jaana. curr.next = l1 or l1 zaroor karo.
Infinite loop: curr = curr.next bhool jaana toh infinite loop. Har iteration mein curr advance karo.
Stability issue: l1.data < l2.data ki jagah l1.data <= l2.data use karo taaki equal values ki order maintain rahe (stable sort).

Lesson complete?

Merge sorted lists seekh liye✓ Ab top linked list problems dekhte hain � ye problems interview mein sabse zyada poochte hain.