Interview Q&A / Data Structures & Algorithms

1. How do you reverse a singly linked list?

   Walk through the list once with three pointers (previous, current and next) and turn each arrow around so it points backwards. The last node you visit becomes the new head. O(n) time, O(1) extra space.

   BeginnerIn-depthCoding2 min read
2. How do you detect a cycle in a linked list?

   Use Floyd's tortoise and hare method. Move a slow pointer one step and a fast pointer two steps at a time. If the fast pointer reaches null, there is no cycle. If the two pointers ever meet, there is a cycle. It runs in O(n) time with O(1) extra space.

   IntermediateIn-depthCoding4 min read