DSA Sheet - Day 11 Linked List

🚀 DSA Sheet – Day 11: Linked List (Part 1)

Linked Lists test pointer manipulation and memory understanding. Mastering these problems will strengthen your fundamentals for many advanced topics.

📊 Progress Tracker

Progress: 0 / 6 Completed

Done	Problem	Practice	Level	Companies
	Middle of Linked List	Solve	Easy	Meta, Qualcomm
	Reverse Linked List	Solve	Easy	Google, TCS
	Detect Cycle in Linked List	Solve	Easy	Amazon, Cisco
	Remove Cycle in Linked List	Solve	Medium	Amazon, Microsoft
	Merge Two Sorted Linked Lists	Solve	Easy	Flipkart, FactSet
	Flatten a Linked List	Solve	Hard	Flipkart

🧠 Key Approaches

• Middle of LL: Slow & Fast pointer technique
• Reverse LL: Iterative pointer reversal
• Detect Cycle: Floyd’s Cycle Detection (Tortoise & Hare)
• Remove Cycle: Find starting point of loop and break it
• Merge LL: Two pointer merge (like merge sort)
• Flatten LL: Merge multiple sorted linked lists

⚡ Quick Cheatsheet

Reverse Linked List

ListNode* prev = NULL;

while(head){
  ListNode* next = head->next;
  head->next = prev;
  prev = head;
  head = next;
}

return prev;
    

Detect Cycle (Floyd’s Algorithm)

ListNode *slow = head, *fast = head;

while(fast && fast->next){
  slow = slow->next;
  fast = fast->next->next;

  if(slow == fast) 
    return true;
}
    

Merge Two Sorted Linked Lists

ListNode dummy;
ListNode* tail = &dummy;

while(l1 && l2){
  if(l1->val < l2->val){
    tail->next = l1;
    l1 = l1->next;
  } else {
    tail->next = l2;
    l2 = l2->next;
  }
  tail = tail->next;
}

tail->next = l1 ? l1 : l2;
    

🔥 Pro Tip

Linked List problems revolve around pointer control:

• Track previous, current, and next nodes carefully
• Draw diagrams before coding
• Master slow-fast pointer patterns

If you control pointers well, most problems become straightforward.

🏠 All Days ⬅ Previous Next ➡