Linked List Path Sum
You are given a sequence of N integers, representing nodes in a linked list. For each node i (0-indexed), the value a[i] represents the index of the next node. The list might contain a cycle. You start at node 0. Calculate the sum of values of nodes visited before the first time a node is visited again. If the list does not form a cycle and ends (a node points to -1), the sum should include all nodes from the start until the end.
Input
The first line contains an integer N. The second line contains N space-separated integers a_0, a_1, ..., a_{N-1}.
Output
Print a single integer: the sum of values of the nodes visited before a node is revisited or the list ends.
Constraints
1 <= N <= 200000. 0 <= a[i] < N or a[i] == -1.
Example 1
5 1 2 3 4 1
5
Starts at 0, goes to 1, then 2, then 3, then 4. Next is 1, which is a repeat. Sum = 5 (nodes 0,1,2,3,4).
Example 2
3 1 2 -1
3
Starts at 0, goes to 1, then 2. Next is -1, list ends. Sum = 3 (nodes 0,1,2).
Hints
Similar problems
- Find Duplicate Cycle EntryMedium
- Cycle Detection and RendezvousMedium
- Find First Duplicate Entry PointMedium
- Find Duplicate Jump TargetMedium
- Array Linked List SimulationMedium
- Linked List Jump GameMedium
More topics: Hash Map and Hashing problems, Linked List problems, Graphs, BFS and DFS problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 1
3 1 2 -1