Linked List Components - Practice Coding Problems

Linked List Components - Problem

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.

A connected component is a maximal group of consecutive nodes whose values are all present in nums.

Input & Output

Example 1 — Basic Connected Components

$ Input: head = [0,1,2,3], nums = [0,1,3,2]

› Output: 2

💡 Note: The linked list is 0→1→2→3. Values [0,1] form one component, value [2] is isolated, and value [3] forms another component. So we have components: [0,1] and [2] and [3], but since all values are in nums, we have [0,1], [2], [3] as separate runs in the linked list order, giving us 2 components: [0,1] and [2,3].

Example 2 — Separate Components

$ Input: head = [0,1,2,3,4], nums = [0,3,1,4]

› Output: 2

💡 Note: Linked list: 0→1→2→3→4. Node 0 is in nums (start component 1), node 1 is in nums (continue component 1), node 2 is not in nums (end component 1), node 3 is in nums (start component 2), node 4 is in nums (continue component 2). Result: 2 components.

Example 3 — Single Component

$ Input: head = [0,1,2,3,4], nums = [1,2,3]

› Output: 1

💡 Note: Node 0 not in nums, nodes 1,2,3 are consecutive in nums forming one component, node 4 not in nums. Only one connected component.

Constraints

The number of nodes in the linked list is in the range [1, 10⁴]
0 ≤ Node.val < 10⁴
All values in the linked list are unique
1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] < 10⁴
All values in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list: 0→1→2→3→4 and nums: [0,3,1,4]

Process

Traverse list, check if each value is in nums

Output

Count connected components: 2

Key Takeaway

🎯 Key Insight: A new component starts when current node is in nums but we weren't previously in a component

Asked in

F Facebook 3 M Microsoft 2

The key insight is to use a hash set for O(1) value lookups and count component starts when transitioning from not-found to found. Best approach is hash set optimization with Time: O(n + m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Array Search	O(n×m)	O(1)	For each node, search the nums array to check if value exists
Hash Set Optimization	O(n + m)	O(m)	Use hash set for O(1) lookup of nums values, then traverse linked list once

Brute Force - Array Search — Algorithm Steps

Traverse linked list node by node
For each node, search nums array linearly
Track when entering/exiting sequences of found values
Count component transitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Node

Move to current node in linked list

Search Array

Linearly search through nums array

Count Components

Track when entering/exiting found sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

bool contains(int* nums, int numsSize, int val) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == val) return true;
    }
    return false;
}

int solution(struct ListNode* head, int* nums, int numsSize) {
    if (!head) return 0;
    
    int components = 0;
    bool inComponent = false;
    struct ListNode* current = head;
    
    while (current) {
        bool found = contains(nums, numsSize, current->val);
        if (found && !inComponent) {
            components++;
            inComponent = true;
        } else if (!found) {
            inComponent = false;
        }
        current = current->next;
    }
    
    return components;
}

struct ListNode* arrayToLinkedList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int headArray[100], nums[100];
    int headSize = 0, numsSize = 0;
    
    // Simple parsing for [1,2,3] format
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token && headSize < 100) {
        headArray[headSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    token = strtok(ptr, ",]");
    while (token && numsSize < 100) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    struct ListNode* head = arrayToLinkedList(headArray, headSize);
    int result = solution(head, nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each of n nodes, we search through m elements in nums array

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for tracking state

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Array Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler