Linked List Cycle

Consider the sequence of numbers x[0], x[1], ..., x[n-1], generated with the next formula:

x[0] = $p$,

x[i] = ($a$ * x[i-1] * x[i-1] + $b$ * x[i-1] + $c$) mod $m$, where $0$ < $i$ < $n$

Create a Linked List from these numbers: List = x[0] → x[1] → ... → x[n-1].

Let $k$ = x[n] mod $n$. If x[n] < $m$ / $2$, let tail → next of your list point to the $k$-th element. Otherwise tail → next = NULL. Setup the value of tail → next according to this condition.

Consider the example: $p$ = $1$, $a$ = $1$, $b$ = $1$, $c$ = $1$, $m$ = $100$, $n$ = $5$. Here List = $1$ → $3$ → $13$ → $83$ → $73$, x[n] = $3$, so $k$ = $3$ < $100$ / $2$ = $m$ / $2$ and tail → next points to the third element that equals $83$ (elements' positions in a List starts from $0$).

Write a method hasCycle that determines if a List has a cycle in it.

Write the code according to the next interface:

class Node
{
public:
    int data;
    Node *next;
    Node() : next(NULL) {};
    Node(int data, Node *next = NULL) : data(data), next(next) {};
};

class List 
{
public:
    Node *head, *tail;
    List() : head(NULL), tail(NULL) {};
    void addToTail(int val); // Add number val to the end of the Linked List
    int hasCycle(void); // Returns 1 if a List has a cycle, and 0 otherwise
};

You can create (use) additional methods if needed.