Lesson 5 � Intermediate-Advanced

Top Linked List Problems

Ab tak sab basic concepts seekh liye � ab real interview problems dekhte hain. Ye 10 problems linked list section mein sabse zyada poochte hain. Har problem ke saath approach, code, aur common mistakes cover karenge.

? 28 min✓ Intermediate-Advanced✓ All linked list basics

Problem Patterns samjho

Two Pointer Pattern

Do pointers use karo � ek aage, ek peeche. Ya ek fast, ek slow. Jaise cycle detection, nth node from end, intersection point. Ye linked list ka sabse common pattern hai.

Fast-Slow Pattern

Slow pointer ek step, fast pointer do steps. Middle finding, cycle detection, palindrome check. Jab tumhe "middle" ya "cycle" ya "half" se related kuch chahiye � ye pattern lagao.

Dummy Node PatternEk dummy node banao jo result list ka starting point hai. Merge, add two numbers, remove elements � jab bhi naya list banana ho with special cases � dummy node se clean code hota hai.

Runner Technique: Runner technique fast-slow pointer ka advanced version hai. Ek pointer fast chalta hai (2 steps), doosra slow (1 step). Isse tumhe middle, cycle, ya distance based problems mein help milti hai. Interview mein 70% linked list problems is pattern pe based hote hain.

Problem 1: Reverse Linked List

Ye sabse fundamental problem hai. Iterative aur recursive dono approaches jaanna zaroori hai.

# Problem: Linked list ko reverse karo
# Input: 1 ? 2 ? 3 ? 4 ✓ None
# Output: 4 ? 3 ? 2 ? 1 ✓ None

# Iterative � O(n) time, O(1) space
def reverse(head):
 prev = None
 current = head
 while current:
 next_node = current.next
 current.next = prev
 prev = current
 current = next_node
 return prev

# Recursive � O(n) time, O(n) space
def reverse_recursive(head):
 if not head or not head.next:
 return head
 new_head = reverse_recursive(head.next)
 head.next.next = head
 head.next = None
 return new_head

Problem 2: Detect Cycle

Floyd's algorithm already seekha � ye problem hai. Interview mein ye as-is poochte hain.

# Problem: Linked list mein cycle hai ya nahi?
# Input: 1 ? 2 ? 3 ? 4 ? 2 (cycle)
# Output: True

def has_cycle(head):
 slow = fast = head
 while fast and fast.next:
 slow = slow.next
 fast = fast.next.next
 if slow == fast:
 return True
 return False

# Bonus: Cycle ka start point
def cycle_start(head):
 slow = fast = head
 while fast and fast.next:
 slow = slow.next
 fast = fast.next.next
 if slow == fast:
 slow = head
 while slow != fast:
 slow = slow.next
 fast = fast.next
 return slow
 return None

Problem 3: Merge Two Sorted Lists

Dummy node technique ka best example. Merge sort ka building block bhi hai.

# Problem: Do sorted lists ko merge karo
# Input: [1,3,5], [2,4,6]
# Output: [1,2,3,4,5,6]

def merge(l1, l2):
 dummy = Node(0)
 curr = dummy
 while l1 and l2:
 if l1.data <= l2.data:
 curr.next = l1
 l1 = l1.next
 else:
 curr.next = l2
 l2 = l2.next
 curr = curr.next
 curr.next = l1 or l2
 return dummy.next

Problem 4: Remove Nth From End

Two pointer technique ka classic example. Ek pointer n steps aage bhejo, phir dono saath chalo � jab fast end tak pahunchega, slow nth node pe hoga.

# Problem: End se Nth node remove karo
# Input: 1 ? 2 ? 3 ? 4 ? 5, n = 2
# Output: 1 ? 2 ? 3 ? 5 (4 remove hua)

def remove_nth_from_end(head, n):
 dummy = Node(0)
 dummy.next = head
 
 # Fast ko n+1 steps aage bhejo
 fast = dummy
 for _ in range(n + 1):
 fast = fast.next
 
 # Slow ko dummy pe rakho
 slow = dummy
 
 # Dono saath chalo � fast end tak jaaye
 while fast:
 slow = slow.next
 fast = fast.next
 
 # Slow ab nth node ke pehle hai � skip karo
 slow.next = slow.next.next
 return dummy.next

Trick: Fast pointer ko n+1 steps aage bhejte hain (not n) kyunki hume nth node ke pehle wala node chahiye. Dummy node use karo special case handle karne ke liye � agar head hi remove karna ho toh.

Problem 5 & 6: Intersection and Palindrome

# Problem 5: Do lists ka intersection point dhundho
# Two lists jahan merge hoti hain woh point chahiye
def get_intersection(l1, l2):
 # Dono pointers ko traverse karao
 # Jab dono None ho jaayein, wapas start pe
 # Ab dono equal distance pe hain � milenge
 p1, p2 = l1, l2
 while p1 != p2:
 p1 = p1.next if p1 else l2
 p2 = p2.next if p2 else l1
 return p1

# Problem 6: Linked list palindrome hai ya nahi?
# Fast-slow se middle dhundho, reverse second half, compare karo
def is_palindrome(head):
 # Step 1: Middle find karo
 slow = fast = head
 while fast and fast.next:
 slow = slow.next
 fast = fast.next.next
 
 # Step 2: Second half reverse karo
 prev = None
 while slow:
 nxt = slow.next
 slow.next = prev
 prev = slow
 slow = nxt
 
 # Step 3: Compare first and second half
 left, right = head, prev
 while right:
 if left.data != right.data:
 return False
 left = left.next
 right = right.next
 return True

Problem 7 & 8: Add Two Numbers and Flatten

# Problem 7: Do numbers ko linked list mein add karo
# Input: (2 ? 4 ? 3) + (5 ? 6 ? 4) = 342 + 465 = 807
# Output: 7 ? 0 ? 8
def add_two_numbers(l1, l2):
 dummy = Node(0)
 curr = dummy
 carry = 0
 
 while l1 or l2 or carry:
 val = carry
 if l1:
 val += l1.data
 l1 = l1.next
 if l2:
 val += l2.data
 l2 = l2.next
 
 carry = val // 10
 curr.next = Node(val % 10)
 curr = curr.next
 
 return dummy.next

# Problem 8: Flatten a multilevel linked list
# Har node ke paas child bhi ho sakta hai � sab flatten karo
def flatten(head):
 if not head:
 return head
 
 curr = head
 while curr:
 if curr.child:
 # Child ko merge karo
 child_head = flatten(curr.child)
 next_node = curr.next
 
 curr.next = child_head
 child_tail = child_head
 while child_tail.next:
 child_tail = child_tail.next
 child_tail.next = next_node
 
 curr.child = None
 curr = curr.next
 
 return head

Problem 9 & 10: Copy List with Random Pointer and LRU Cache

# Problem 9: Random pointer wali list ka deep copy
# Har node mein ek random pointer bhi hai � usse bhi copy karo
class RandomNode:
 def __init__(self, val):
 self.val = val
 self.next = None
 self.random = None

def copy_random_list(head):
 if not head:
 return None
 
 # Step 1: Har node ke baad uska copy daal do
 curr = head
 while curr:
 copy = RandomNode(curr.val)
 copy.next = curr.next
 curr.next = copy
 curr = copy.next
 
 # Step 2: Copy ka random point karo
 curr = head
 while curr:
 if curr.random:
 curr.next.random = curr.random.next
 curr = curr.next.next
 
 # Step 3: Original aur copy lists alag karo
 dummy = RandomNode(0)
 copy_curr = dummy
 curr = head
 while curr:
 copy_curr.next = curr.next
 copy_curr = copy_curr.next
 curr = curr.next.next
 
 return dummy.next

# Problem 10: LRU Cache (concept)
# Least Recently Used cache � O(1) get aur put
# Doubly linked list + HashMap use hota hai
# Most recently used ko head pe, least used ko tail pe

LRU Cache Pattern: LRU Cache two data structures combine karta hai � HashMap for O(1) lookup aur Doubly Linked List for O(1) insertion/deletion. Jab bhi access ho koi key, usse head pe move karo. Jab cache full ho, tail se remove karo (least recently used).

Try it: code khud likho

Exercise

Question: List [1,2,3,4,5] mein end se 2nd node remove karo. Final list likho.

Question: Linked list [1,2,1] palindrome hai? "Yes" ya "No" mein answer do.

Common mistakes

Not using dummy node: Dummy node use nahi karna � special cases handle karna mushkil ho jaata hai. Hamesha naya list banana ho toh dummy se start karo.
Losing references: Pointer change karne se pehle next node save karna bhool jaana. Hamesha next_node = current.next pehle karo.
Off-by-one in nth from end: Fast pointer ko n steps nahi, n+1 steps aage bhejna hai kyunki hume pehle wala node chahiye.
Not handling empty list: Head None hai toh special case handle karo. Pehle if not head check karo.
Recursion stack overflow: Bahut badi list ke liye recursion O(n) stack space leta hai. Iterative approach preferred hai production mein.

Module complete!

Congratulations! Linked Lists ka pura module complete ho gaya. Ab Trees ka next module start karo � trees basically linked lists ka extension hain with branching. Keep grinding!

Back to Roadmap ?