DSA Sheet - Day 12 Linked List
🚀 DSA Sheet – Day 12: Linked List (Part 2)
This section focuses on advanced linked list manipulations like reversing in groups, cloning complex structures, and pointer-heavy transformations.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Palindrome Linked List | Solve | Easy | Google, Uber | |
| Clone List with Random Pointer | Solve | Medium | Oracle, Nvidia | |
| Reverse Linked List II | Solve | Medium | Amazon, Microsoft | |
| Add Two Numbers | Solve | Medium | Amazon, Google | |
| Reverse Nodes in K Group | Solve | Hard | Amazon, Apple | |
| Rotate Linked List | Solve | Medium | Amazon |
🧠 Key Approaches
- Palindrome LL: Find middle → reverse second half → compare
- Clone Random Pointer: Interleave nodes → assign random → separate
- Reverse LL II: Reverse sublist using pointer manipulation
- Add Two Numbers: Digit-by-digit addition with carry
- Reverse K Group: Reverse nodes in chunks of size k
- Rotate LL: Make list circular → break at correct position
⚡ Quick Cheatsheet
Palindrome Linked List
// 1. Find middle (slow-fast)
// 2. Reverse second half
// 3. Compare both halves
Add Two Numbers
int carry = 0;
while(l1 || l2 || carry){
int sum = carry;
if(l1) sum += l1->val, l1 = l1->next;
if(l2) sum += l2->val, l2 = l2->next;
carry = sum / 10;
// create new node with sum % 10
}
Reverse Nodes in K Group
// check if k nodes exist
// reverse k nodes
// connect with next group
🔥 Pro Tip
Advanced linked list problems test pointer mastery:
- Always track prev, current, next carefully
- Break problem into smaller pointer operations
- Draw diagrams before coding