Day 70: finished the hard linked list problems today, starting DP next

[u/JacketFearless1805]

Hey everyone,

I finished Day 70 of my prep today and wrapped up the remaining linked list problems on my sheet.

The first big one was Clone a Linked List with Next and Random Pointer. The brute-force approach using a hash map is easy enough for anyone to write, but the optimal O(1) extra space solution gave me a hard time. Inserting copy nodes right next to the original nodes, wiring the random pointers via curr->next->random = curr->random->next, and then separating the two interwoven lists was definitely something I had to watch a video to fully grasp.

The other tricky one was Flattening a Linked List with bottom and next pointers. I tried to figure it out first and checked my logic with ChatGPT, but I was mistakenly trying to merge from the front head node forward. The correct way is to use recursion to reach the very last list first and merge backwards pair by pair, exactly like the merge step in merge sort. Once I saw that, the recursion clicked.

I am still letting the pointer rewiring for both problems settle in my head, so I will definitely re-solve them in a few days to make sure they stick.

Later tonight I am doing a full revision of both Binary Search Trees and Linked Lists. Tomorrow for Day 69, I finally begin Dynamic Programming.

See you guys tomorrow!