Skip to main content
Talentd

Linked List Components - Solution & Explanation

MediumArrayHash TableLinked List14 min readAsked at: Amazon, Uber, Google +1
Practice this problem

Problem Statement

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.

Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.

 

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

 

Constraints:

  • The number of nodes in the linked list is n.
  • 1 <= n <= 104
  • 0 <= Node.val < n
  • All the values Node.val are unique.
  • 1 <= nums.length <= n
  • 0 <= nums[i] < n
  • All the values of nums are unique.

Approach Overview

Problem Overview: You are given the head of a linked list and an array nums containing a subset of node values. A component is a group of consecutive nodes in the list where every node value appears in nums. The task is to count how many such connected components exist.

Approach 1: Set for Quick Lookup (O(n) time, O(k) space)

The cleanest solution uses a hash table (set) to quickly check whether a node value exists in nums. Insert all values from nums into a set, then iterate through the linked list once. When the current node value exists in the set and the next node either does not exist in the set or is null, you found the end of a component. Increment the counter. The key insight: each component is counted exactly once at its boundary (the last node belonging to that component). Membership checks become O(1) due to hashing, so the full traversal remains linear. This approach is straightforward and performs well even when nums is large.

Approach 2: Two-Pass on Linked List without Extra Space (O(n * k) time, O(1) space)

If you want to avoid additional memory, skip the hash set and work directly with the array nums. Traverse the linked list and determine membership by scanning the nums array each time you need to check if a value belongs to the subset. Similar to the set approach, you detect a component when the current node value exists in nums and the next node either does not belong to nums or is null. Because each membership test scans the array, the complexity becomes O(n * k), where k is the size of nums. The benefit is constant extra space. This works when nums is small or memory usage is tightly constrained.

Recommended for interviews: The hash set approach is what most interviewers expect. It demonstrates that you recognize the repeated membership check and optimize it with constant-time lookups. Mentioning the no-extra-space variation shows awareness of trade-offs, but the O(n) hash set solution best balances clarity and efficiency.

Approach 1: Set for Quick Lookup

This approach leverages a set data structure to quickly determine if a node from the linked list is part of the 'nums' array. We traverse the linked list and use the set to track connected components. If a node is found in the set and it is not part of an ongoing component, we start a new component and continue the counter until we find a break in connectivity.

This C implementation uses an array as a simple hashset to mark elements present in 'nums'. We iterate through the linked list and check if each node value exists in the hashset. We maintain a boolean flag 'in_component' to track if we are currently traversing a connected component of 'nums'. Whenever we reach a node from 'nums' not preceded by another node in 'nums', we increment our component counter.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'.
Space Complexity: O(n) due to the hashset used for quick lookup.

Try this approach in the editor →

Approach 2: Two-Pass on Linked List without Extra Space (Optimized for nums)

This alternative approach first marks the initial position of all nodes existing in 'nums' by setting their value offsets to a special marker. In a second pass, it counts connected sequences between marked nodes. This enables direct marking of active components without extra space dedicated to hashes or sets but works best only when the linked list structure is such that in-place marking is feasible.

The C implementation performs list traversal to adjust node values based on component existence (conceptually), with a boolean counter tracking transitions into distinct components. As the standard C language lacks facilities for safe in-place data marking via addresses directly, memory strategy handled here targets traversal adjustments for ideal step-by-step reference marking. (Note: abstract — typically requires head management outside if values manipulate!)

Code

C (with assumption modifications)Python

C (with assumption modifications)

Python

Complexity

Time Complexity: O(n * m), as repeated search across elements within restricted logic.
Space Complexity: O(1), maintaining constant markers within node itself, with ideal suggesting!

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Set for Quick Lookup

Time Complexity: O(n + m), where n is the length of the linked list, and m is the length of 'nums'.
Space Complexity: O(n) due to the hashset used for quick lookup.

Two-Pass on Linked List without Extra Space (Optimized for nums)

Time Complexity: O(n * m), as repeated search across elements within restricted logic.
Space Complexity: O(1), maintaining constant markers within node itself, with ideal suggesting!

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set for Quick LookupO(n + k)O(k)General case. Fast membership checks using a hash set.
Two-Pass without Extra SpaceO(n * k)O(1)Useful when memory is constrained or nums size is very small.

Video Solution

817. Linked List Components | LEETCODE MEDIUM | LINKED LIST • code Explainer • 4,108 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Linked List Components easy or hard?
Linked List Components is considered a medium-level problem on LeetCode with an acceptance rate around 58%. The challenge lies in recognizing component boundaries and using a hash set to avoid repeated membership scans.
Linked List Components Python/Java solution
Python and Java solutions typically build a HashSet or set from nums and iterate through the linked list. When a node is in the set and the next node is not, increment the component count. This implementation runs in O(n) time and is the standard interview solution.
How to solve Linked List Components in O(n)?
Insert all values from nums into a hash set. Traverse the linked list and check if the current node value is in the set while the next node value is not. Each such boundary marks the end of a component, so increment the counter. Because each node is processed once, the total complexity is linear.
What is the best approach for Linked List Components?
The most efficient approach uses a hash set to store all values from nums and then traverses the linked list once. When a node value is in the set and the next node is not, you count a component boundary. This runs in O(n) time with O(k) extra space, where k is the size of nums.
Is Linked List Components asked at Google/Amazon/Meta?
Linked list and hash set combination problems appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests recognition of connected segments and efficient membership lookup using hashing.
What data structure is used in Linked List Components?
The primary data structure used is a hash set for constant-time membership checks. The problem also requires traversal of a singly linked list and understanding how consecutive nodes form components.
What is the time complexity of Linked List Components?
The optimal solution runs in O(n + k) time, where n is the number of nodes in the linked list and k is the size of nums. Each node is visited once and set membership checks take O(1) on average.

Ready to solve this problem?

Practice Linked List Components with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Nodes in Between Zeros