Linked List Components

MediumLinked Listhashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the head of a linked list whose node values are **distinct** integers in the range [0, n - 1], where n is the number of nodes. You are also given an array nums containing a subset of those values (each at most once, in any order). A *component* is a maximal run of **consecutive nodes in the list** whose values all appear in nums. Two chosen values belong to the same component only if their nodes are adjacent in the list (directly or through other chosen nodes); being adjacent in nums means nothing. Return the number of components.

Examples

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Nodes 0 and 1 are adjacent and both chosen, forming one component. Node 3 is cut off by node 2, forming a second.
Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
The runs are 0 -> 1 and 3 -> 4.

Constraints

  • `1 <= n <= 10^4`
  • `0 <= Node.val < n`, and all node values are distinct.
  • `1 <= nums.length <= n`
  • All values in `nums` are distinct and appear in the list.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems