主观题：List ranking problem

Given a linked list of $$n$$ elements which are stored in an array $$A$$ of size $$n$$.  Each element, except one (to be called **last**), has a pointer to its successor in
the list; also, each element, except one (to be called **first**), is the successor of exactly one element in the list. 

Define $$rank(i)$$ as follows: for each $$i$$, $$rank(i) = 0$$ if $$next(i) = $$NIL (or “end-of-list”) and $$rank(i) = rank(next(i)) + 1$$ otherwise. 

The task is to compute $$rank(i)$$ for every $$i$$.  Please 

1. design a linear time serial algorithm; and 
2. design a parallel algorithm

for solving the problem.  Please analyse the complexities.





答案：