Linked List Jumps

Description

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.

Constraints:

• n ≤ 100,000 where n is the number of nodes in node

Example 1

Input

node = [2, 1, 4, 1]

Output

[2, 4]

Explanation

Note that 2's next is 2 node ahead. 4's next is out of bounds, so it's set to null.

---

Intuition

Implementation

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public LLNode solve(LLNode node) {
        int steps;
        LLNode head = node;
        while (node != null) {
            steps = node.val;
            for (int i = 1; i < steps; i++) {
                if (node.next != null) {
                    node.next = node.next.next;
                } else {
                    break;
                }
            }
            node = node.next;
        }
        return head;
    }
}

Complexity

• Time: O(n)
• Space: O(1)