Implement list cloning and k-frequency finder

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.