Solve linked-list and top-K algorithm tasks

Question

Given a singly linked list, return the k-th node counted from the end.

Given an integer array, return the top k most frequent numbers.

Given a list of points on the 2-D plane, return the k points closest to the origin (0, 0).

Given a string where adjacent identical characters "collide" and disappear repeatedly (e.g., "abbba" → "aa" → ""), output the final string after all collisions are resolved.

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ https://leetcode.com/problems/top-k-frequent-elements/description/ https://leetcode.com/problems/k-closest-points-to-origin/description/ https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/

Kth Node From the End of a Linked List

Given a singly linked list (provided here as a list of node values in order) and an integer k, return the value of the k-th node counted from the END of the list (k = 1 is the last node). Return null if k is out of range (k < 1 or k > length).

Classic two-pointer / runner technique: advance a fast pointer k steps ahead, then move both fast and slow until fast reaches the end; slow lands on the k-th node from the end. Here the list is modeled as an array of values so the function takes (values, k).

Example: values = [1, 2, 3, 4, 5], k = 2 -> 4 (the 2nd node from the end).

Constraints

• 1 <= number of nodes <= 10^4
• Node values fit in a 32-bit signed integer
• 1 <= k, but k may exceed the list length (return null in that case)

Hints

1. Think of two pointers: move a fast pointer k steps ahead first.
2. Then advance fast and slow together until fast falls off the end; slow is now at the k-th node from the end.
3. Equivalently, the k-th node from the end is at 0-based index n - k from the front.

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. To make the output deterministic, return them ordered by frequency descending; break ties by the numeric value ascending.

Count frequencies with a hash map, then select the top k. A bucket sort by frequency, or a heap, achieves better-than-O(n log n) selection, but any correct ordering that respects the tie-break rule above is accepted by these tests.

Example: nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] (1 appears 3x, 2 appears 2x).

Constraints

• 1 <= nums.length <= 10^5
• Values fit in a 32-bit signed integer
• 1 <= k <= number of distinct values in nums
• Tie-break: equal frequencies ordered by value ascending

Hints

1. Count occurrences with a hash map first.
2. You don't need to fully sort: a min-heap of size k, or bucket sort indexed by frequency, gives the top k efficiently.
3. For deterministic output, break frequency ties by the smaller value.

K Closest Points to the Origin

Given a list of points on the 2-D plane (each point is [x, y]) and an integer k, return the k points closest to the origin (0, 0), measured by Euclidean distance. Compare using squared distance xx + yy to avoid floating point. To make the output deterministic, order the returned points by squared distance ascending, then by x ascending, then by y ascending.

A max-heap of size k, or a quickselect partition, finds the k closest in better than full-sort time, but any correct selection respecting the tie-break order above is accepted.

Example: points = [[1, 3], [-2, 2]], k = 1 -> [[-2, 2]] (distance^2 8 < 10).

Constraints

• 1 <= points.length <= 10^4
• Coordinates fit in a 32-bit signed integer
• 1 <= k <= points.length
• Use squared distance to compare; tie-break by x then y ascending

Hints

1. Compare by squared distance xx + yy — no need for sqrt.
2. A max-heap of size k keeps the k smallest distances seen so far.
3. Quickselect partitions around the k-th smallest distance in O(n) average time.

Collapse Adjacent Identical Characters Until Stable

Given a string s, repeatedly remove every maximal run of two or more adjacent identical characters. Removing a run can bring new characters next to each other, which may form new runs; keep collapsing until no run of length >= 2 remains. Return the final string (which may be empty).

Example: "abbba" -> the run "bbb" disappears -> "aa" -> the run "aa" disappears -> "" (empty string).

A single left-to-right pass with a stack of (character, run-length) handles the cascading correctly: each time the top of the stack reaches a run, drop it and let the characters on either side become adjacent.

Constraints

• 0 <= s.length <= 10^5
• s consists of lowercase (and/or uppercase) letters
• A run of length >= 2 is removed entirely, not pairwise
• Removal cascades: collapsing may create new runs that must also be removed

Hints

1. Maintain a stack of (character, count) pairs as you scan left to right.
2. When the incoming character matches the stack top, increment its count; when a count reaches the run threshold, remove that entry.
3. After removing an entry, the new top and the next incoming character may match — that is the cascade, and the stack handles it automatically.