7. Algorithm Design: Finding Cycles Give pseudocode for an algorithm which takes

Question

7. Algorithm Design: Finding Cycles Give pseudocode for an algorithm which takes as input a singly-linked-list 2 (of un- known size, possibly containing loops) and returns True if the singly-linked-list has a loop, and False if the singly-linked-list has no loops. To simplify things, you may assume that each node of the linked-list stores an integer value, and the integers stored at each node of the linked list are distinct. If there are n distinct nodes 3 in the input, show that your algorithm has a worst-case asymptotic runtime bounded by O(n) and worst-case asymptotic space usage bounded by O(1). (***)

Explanation / Answer

Idea: Use Floyd Cycle Finding Algorithm

Explanation:

Algorithm

1) Take two pointers slow_ptr and fast_ptr both pointing to start of the List.

2) slow_ptr will keep on incrementing by 1

3) fast_ptr will keep on incrementing by 2

4) If there is a loop in the list, we will come to a stage where fast_ptr and slow_ptr will ultimately meet and we can say that the linked list has Loop

5) Otherwise of we reach to a stage where slow_ptr is NULL or fast_ptr is NULL means the Linked List has No loop




Complexity : We can see that we iterate the list constant * n time over the corse to find if the List has Cycle in it.
So Overall complexity is O(n)

PseudoCode


Algorithm FindCycles (head )

START

slow_ptr = head , fast_ptr = head

    while slow_ptr && fast_ptr && fast_ptr->next

        slow_ptr = slow_ptr->next

        fast_ptr = fast_ptr->next->next

        if (slow_ptr == fast_ptr)

            return True

    return False

END

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.