You are given two separate coding tasks. --- ### Problem 1: Deep copy a linked list with extra pointers You are given the head of a singly linked list. Each node has three fields: - `val`: an integer value - `next`: a pointer (or reference) to the next node in the list, or `null` if it is the last node - `random`: a pointer (or reference) to **any** node in the list (including possibly itself) or `null` The list may contain zero or more nodes. **Task:** Implement a function that creates a **deep copy** of this list. The new list must: - Contain the same number of nodes as the original. - Preserve the `val` values. - Preserve the structure of both the `next` and `random` pointers: for every original node, its copy's `next` and `random` should point to the copies of the corresponding original targets. - Share **no** nodes with the original list (i.e., all nodes in the copied list must be newly allocated). Return the head of the copied list. You may assume: - Number of nodes \(n\) satisfies \(0 \leq n \leq 10^5\). - The input list may contain arbitrary `random` pointer configurations, including cycles formed via `random` pointers. You should aim for \(O(n)\) time complexity and \(O(n)\) additional space. --- ### Problem 2: Find the k most frequent integers in an array You are given an integer array `nums` and an integer `k` where \(1 \leq k \leq \text{number of distinct elements in } nums\). **Task:** Return any order of the `k` distinct integers that appear **most frequently** in `nums`. - If multiple numbers have the same frequency and they are in the top `k` by frequency, any order among them is acceptable. - The output should contain exactly `k` distinct integers. **Examples** Example 1: - Input: `nums = [1, 1, 1, 2, 2, 3]`, `k = 2` - One valid output: `[1, 2]` (because `1` appears 3 times, `2` appears 2 times, `3` appears 1 time) Example 2: - Input: `nums = [4, 4, 4, 5, 5, 6]`, `k = 1` - One valid output: `[4]` (since it is the most frequent element) You may assume: - \(1 \leq \text{length of } nums \leq 10^5\) - \(-10^9 \leq nums[i] \leq 10^9\) - The number of distinct values in `nums` is at least `k`. Aim for an algorithm that runs in **better** than \(O(n \log n)\) time, where \(n\) is the length of `nums`.