- Give a linear time algorithm to solve the circular-list-detection problem (CLD):
Input: A, an array of tuples (v, i), where v is some data and i is an index of a location in the array or -1 to indicate null. Each tuple is a node of a linked list where v is the data inside the node and i is a pointer to the next node in the list. You may assume that -1ilength(A), i.e., that every second item in a tuple is a valid index of the array A.
Output: YES if any linked list represented by tuples in A is circular, NO otherwise.
Example Input 1: A = [(x, 2), (x, -1), (x, 3), (x, 0), (x, 4)]
Example Output 1: YES
Example Input 2: A = [(x, 2), (x, -1), (x, 3), (x, -1), (x, 1)]
Example Output 2: NO
Your solution must:
- must solve CLD
- Provide an explanation of how your algorithm works
- Formal pseudocode of the algorithm
- A proof that the algorithm is correct
- A symbolic runtime analysis of the algorithm
0 comments