list types some of the key methods on these lists include returning the head/tailadding an element at the head/tailreturning the value stored at the head/tailand deleting the headtailor arbitrary node in the list test for cyclicity although linked list is supposed to be sequence of nodes ending in nullit is possible to create cycle in linked list by making the next field of an element reference to one of the earlier nodes write program that takes the head of singly linked list and returns null if there does not exist cycleand the node at the start of the cycleif cycle is present (you do not know the length of the list in advance hintconsider using two iteratorsone fast and one slow solutionthis problem has several solutions if space is not an issuethe simplest approach is to explore nodes via the next field starting from the head and storing visited nodes in hash table-- cycle exists if and only if we visit node already in the hash table if no cycle existsthe search ends at the tail (often represented by having the next field set to nullthis solution requires (nspacewhere is the number of nodes in the list brute-force approach that does not use additional storage and does not modify the list is to traverse the list in two loops--the outer loop traverses the nodes one-by-oneand the inner loop starts from the headand traverses as many nodes as the outer loop has gone through so far if the node being visited by the outer loop is visited twicea loop has been detected (if the outer loop encounters the end of the listno cycle exists this approach has ( time complexity this idea can be made to work in linear time--use slow iterator and fast iterator to traverse the list in each iterationadvance the slow iterator by one and the fast iterator by two the list has cycle if and only if the two iterators meet the reasoning is as followsif the fast iterator jumps over the slow iteratorthe slow iterator will equal the fast iterator in the next step nowassuming that we have detected cycle using the above methodwe can find the start of the cycleby first calculating the cycle length once we know there is cycleand we have node on itit is trivial to compute the cycle length to find the first node on the cyclewe use two iteratorsone of which is ahead of the other we advance them in tandemand when they meetthat node must be the first node on the cycle the code to do this traversal is quite simpledef has_cycle (head)def cycle_len (end)start step end while truestep + start start next if start is endreturn step fast slow head while fast and fast next and fast next nextslow fast slow next fast next next if slow is fastfinds the start of the cycle