DSA/leetcode (59)

Cut the list in half, reverse the back half, then zip the two chains together one node at a time - three solved problems stacked on top of each other.

A hash map for O(1) lookup and a doubly linked list for O(1) reordering, pointed at the same nodes - plus the std::list version where splice does the rewiring for you.

Merge sort is the one comparison sort a linked list actually wants, and the bottom-up form merges runs of width 1, 2, 4, 8 with no recursion and no scratch array.

Merging the lists one at a time walks the growing result k times over - pair them up and halve the count each round instead, and log k rounds finish it.

Three link writes per pair, anchored on a dummy so the node before every pair always exists and the changing head needs no special case.

92 run in a loop - reverse exactly k nodes, stitch the two seams, and hand the group's tail to the next round as its anchor, leaving a short tail untouched.

One list per use count instead of one list overall, plus a minFreq variable that is kept up to date by two rules so eviction never has to search for the smallest count.

Quicksort's partition step lifted out on its own - build two chains by appending, concatenate, and terminate the second one or it loops back into the middle of the list.

Reverse exactly right - left + 1 nodes with the usual loop, then spend the real effort on the two links at the seams that stitch the segment back into the list.

Copying the nodes is the easy half; the real problem is needing a correspondence from each old node to its copy, kept either in a hash map or woven into the list itself.

Two pointers at different speeds close the gap by one node per step inside a loop, so a cycle is detected by a collision rather than by remembering where you have been.

Two walkers that switch lists when they fall off the end, so both cover the same total distance and land on the shared node together.

A gap of n between two pointers turns a distance from the end into a distance from the front, so one pass finds the node to unlink without ever measuring the length.

Reverse order means the digits arrive least significant first, which is exactly the order schoolbook addition wants, so one walk with a carry builds the answer.

Strip the matching prefix first so the head is safe, then unlink matches from behind with a trailing pointer that only advances over survivors.

Walk the list once and flip every next pointer backwards, carrying prev and curr along and saving the next node before each rewire.

A dummy node and a tail pointer, splicing the smaller head across each round and attaching whatever is left in one move.

Twins are the pairs a palindrome check compares, so the machinery from 234 works unchanged - find the middle, reverse the back half, and take a max instead of an equality test.

Two earlier problems glued together - find the middle with the fast pointer, reverse the back half in place, then walk the two halves toward each other.

Two pointers weaving forward, each skipping over the other, splitting the list into an odd chain and an even chain that get spliced together once at the end.

Rotating right by k only moves the cut, not the nodes, so open a gap of k between two pointers and walk them together until the front one lands on the tail.

Hang a dummy node in front of the list so every operation becomes the same walk to the node before the target, then one rewire.

Walk to the end of each run instead of the start, then let the pointer that stayed behind decide whether the run was one node or many.

The write pointer from 26 moved onto a linked list, where keeping an element means pointing the last kept node at it instead of copying.

One pointer moving twice as fast as the other arrives at the end exactly when the slow one reaches the middle, so the length never has to be measured.

Fixed size sliding window that counts vowels, updating the count by one character out and one character in at each step.

Sliding window holding at most one zero, with the window length minus one as the answer.

Sliding window that grows until the sum reaches the target, then shrinks from the left while it still does.

Fixed size sliding window with a map of counts, taking the sum only when every number in the window is different.

Sliding window that grows to the right and shrinks from the left whenever a character repeats.

Fixed size sliding window with letter counts, tracking how many letters of s1 currently have the right count in the window.

Longest stretch with at most two different values, with a sliding window over a map of counts.

Converging pointers that always discard the shorter wall, because it is the one nothing further inward can rescue.

Converging pointers that skip non-alphanumeric characters in place, so the filtered string is never actually built.

Floyd's cycle detection on an actual linked list - the same two phases as 287, with the null checks a real list needs.

Fix one element, then run the sorted two pointer scan on the rest, skipping equal values to keep triplets unique.

Split on whitespace and join backwards, then the in-place version that reverses the whole string and reverses each word back in O(1) space.

Two pointers from both ends of the sorted array, dropping whichever end can no longer be part of the pair.

Give every battery bigger than the average its own computer, then the remaining batteries can share the remaining computers for exactly total / n minutes.

A write pointer that trails a read pointer, comparing each candidate against the last element kept rather than against its neighbour.

Cyclic sort to put every value at its own index, then the two closed forms - XOR pairing and the Gauss sum - that skip the sorting entirely.

The write pointer pattern with a keep-condition, plus the swap-from-the-end variant that the relaxed ordering requirement allows.

A write pointer for the non-zero prefix, swapping instead of copying so the zeros fill the tail in the same pass.

Read the array as a linked list, then Floyd's cycle detection - the duplicate is the node where the cycle starts, not where the pointers meet.

Cyclic sort with a range guard, so junk outside [1, n] is left where it lies and the first slot not holding its own value is the answer.

Water above a bar is capped by the shorter of the tallest bars on either side, first with one prefix max array, then with two pointers in O(1) space.

Cyclic sort again, reading the occupied mismatched slots instead of the empty ones - the mirror image of 448.

Cyclic sort with a duplicate-safe swap guard, and the sign marking alternative that records presence in the sign bit.

The fixed size sliding window - consecutive windows share k-1 elements, so each step is one add and one subtract instead of a rescan.

Cyclic sort leaves the duplicate stranded in the missing number's slot, so one mismatched index yields both answers at once.

Dutch National Flag - three pointers carving the array into a 0 region, a 1 region, an unknown middle and a 2 region, in one pass.

Count primes below n with the Sieve of Eratosthenes, an odd-only sieve that does half the work, or Lucy_Hedgehog counting in O(n^(3/4)).

Binary exponentiation, squaring the base and multiplying it in for each set bit of the exponent.

Binary search over [0, x] for the largest integer whose square does not exceed x.

The rank of a pair is the union of their edge sets, so it is the sum of two degrees minus one when the pair is joined by a road.

The center sits on every edge, so two edges are enough to identify it.

Build the adjacency list from the edge list, then traverse from the source and check whether the destination is reached.

The judge is the one vertex with in-degree n - 1 and out-degree 0, found by counting degrees on a directed edge list.

Single pass hash map that trades memory for time on the classic pair-sum problem.