Linked List Cycle

Problem Statement

deeksha sharma
Algorithm Problems
1 min readOct 22, 2015

--

Given a linked list, determine if it has a cycle in it. Follow up:
Can you solve it without using extra space?

Approach

Using Floyd Cycle Detection Algorithm, we can find the loop in a linked list. Lets start with 2 pointers

  • Slow pointer that moves 1 node at a time
  • Fast pointer that moves 2 nodes at a time.

Keep moving these pointers until either :

  • Fast pointer becomes null which means that there is no cycle in the linked list.
  • OR
  • Fast pointer and Slow pointer meet which means that there is a cycle.

Note: If there exists a cycle then Slow pointer and Fast pointer will definitely meet. At this point the slow pointer will be inside the loop.

The run time complexity of this Solution is O(n)

--

--

deeksha sharma
Algorithm Problems

Work for https://bonsaiilabs.com/ life long learner ,investing time heavily in personal finance, education, tech and design skills. Twitter: @deekshasharma25