Recursive Algorithm to Compute the Linked List Jumps

You are given a singly linked list node containing positive integers. Return the same linked list where every node’s next points to the node val nodes ahead. If there’s no such node, next should point to null.

Connstraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
node = 1 → 2 → 9 → 4 → 8
Output
1 → 2 → 4

Explanation
Note that 1’s next is 1 node ahead. 2’s next is 2 nodes ahead. 4’s next is out of bounds, so it’s set to null.

Compute the Linked List Jumps via Recursion

Let’s solve a step at a time. Keep the current node and find the next node by skipping the number of nodes (represented by the value). Then, we can recursively solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* node) {
    if (!node) return NULL;
    int jump = node->val;
    auto head = node;
    for (int i = 0; i < jump && (node); ++ i) {
        node = node->next;
    }
    head->next = solve(node);
    return head;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* node) {
    if (!node) return NULL;
    int jump = node->val;
    auto head = node;
    for (int i = 0; i < jump && (node); ++ i) {
        node = node->next;
    }
    head->next = solve(node);
    return head;
}

By pointing the next pointer of the current node (which is the head to return) to the recursive call, we solve the problem. The space complexity is O(N) due to stack usage by recursion. And the time complexity is O(N) as we are going through each node in the linked list.

The Recursive Algorithm that is implemented in Python: Teaching Kids Programming – Linked List Jumps via Recursion

–EOF (The Ultimate Computing & Technology Blog) —