easyLinked ListsPattern: Recursive Approach

Filter Linked List Nodes by Timestamp Solution

Problem Statement

Given the head of a singly linked list, where each node has an integer `val` and an integer `timestamp`. Implement a function `filterNodes(head, targetTimestamp)` that recursively traverses the linked list. The function should collect the `val` of all nodes whose `timestamp` is strictly greater than `targetTimestamp`. The collected `val`s must be returned as a list, maintaining their original order as they appear in the linked list.

Examples

Example 1:

Input:head = [(10, 100), (20, 150), (30, 90), (40, 200), (50, 120)], targetTimestamp = 130

Output:[]

Explanation: Nodes with timestamps 150 and 200 are strictly greater than 130. Their values (20 and 40) are collected in order.

Example 2:

Input:head = [(5, 50), (15, 60), (25, 70)], targetTimestamp = 80

Output:[]

Explanation: All node timestamps (50, 60, 70) are less than or equal to 80. No values are collected.

Constraints

The number of nodes in the list `N` is between `0` and `10^4`.
`0 <= Node.val <= 10^9`
`0 <= Node.timestamp <= 10^9`
`0 <= targetTimestamp <= 10^9`
The solution must use a recursive approach.

Time: O(N) Space: O(N)

The optimal approach maintains the recursive structure but uses an accumulator pattern. This involves either passing a mutable list (e.g., an array or list reference) down through recursive calls, appending elements to it when the condition is met, or building the result during the "return trip" of the recursion using an auxiliary function that collects results into a pre-allocated or efficiently growing list. This ensures each node is processed once and values are collected efficiently, leading to O(N) time complexity.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    int timestamp;
    ListNode *next;
    ListNode(int x, int t) : val(x), timestamp(t), next(nullptr) {}
};

class Solution {
public:
    // Helper recursive function to populate the result vector
    void filterNodesHelper(ListNode* head, int targetTimestamp, std::vector<int>& result) {
        if (head == nullptr) {
            return;
        }

        if (head->timestamp > targetTimestamp) {
            result.push_back(head->val);
        }

        filterNodesHelper(head->next, targetTimestamp, result);
    }

    // Main function to initiate filtering
    std::vector<int> filterNodes(ListNode* head, int targetTimestamp) {
        std::vector<int> result;
        filterNodesHelper(head, targetTimestamp, result);
        return result;
    }
};

// --- Driver Code ---
// Utility to create a linked list from input
ListNode* createLinkedList(const std::vector<std::pair<int, int>>& nodesData) {
    if (nodesData.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(nodesData[0].first, nodesData[0].second);
    ListNode* current = head;
    for (size_t i = 1; i < nodesData.size(); ++i) {
        current->next = new ListNode(nodesData[i].first, nodesData[i].second);
        current = current->next;
    }
    return head;
}

// Utility to delete a linked list
void deleteLinkedList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numNodes;
    std::cin >> numNodes;
    std::cin.ignore(); // Consume the newline after numNodes

    std::vector<std::pair<int, int>> nodesData;
    for (int i = 0; i < numNodes; ++i) {
        std::string line;
        std::getline(std::cin, line);
        std::stringstream ss(line);
        int val, timestamp;
        char comma; // To consume the comma
        ss >> val >> comma >> timestamp;
        nodesData.push_back({val, timestamp});
    }

    int targetTimestamp;
    std::cin >> targetTimestamp;

    ListNode* head = createLinkedList(nodesData);

    Solution sol;
    std::vector<int> filteredVals = sol.filterNodes(head, targetTimestamp);

    if (filteredVals.empty()) {
        std::cout << "[]\n";
    } else {
        std::cout << "[";
        for (size_t i = 0; i < filteredVals.size(); ++i) {
            std::cout << filteredVals[i];
            if (i < filteredVals.size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]\n";
    }

    deleteLinkedList(head); // Clean up allocated memory

    return 0;
}