Linked List Cycle / II Algorithm
Today we will learn how to solve two problems from leetcode – Linked List Cycle and Linked List Cycle II. So, as you can see these problems are related but first easiest and second more complex. OK, first task description:
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
So, it’s easy if you know Robert W. Floyd algorithm also called “tortoise and the hare” algorithm. Full description you can read in wiki. I am going to provide short description before implementation. Main idea of algorithm is two pointers. First one slow or tortoise, second one is fast or hare. Slow pointer will be moved node by node, fast one node after node i.e. twice faster than slow one. So, when slow pointer run through distance x fast 2x and if there is loop fast will catch up slow, this is rule to stop loop.
OK, try to implement it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 /** * Definition for singlylinked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(slow.equals(fast)){ return true; } } return false; } } /** * Definition for singlylinked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(slow.equals(fast)){ return true; } } return false; } } 
You can see that is very easy to develop and understand. OK, let’s move to the second task:
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null
.Follow up:
Can you solve it without using extra space?
This task is more complex, because you should find start cycle node. But if you again read tortoise and the hare algorithm you should understand this is not so hard.
Short transcript of the wiki description:
When fast caught slow, slow is stay in the same distance to first cycle node as from start to first cycle node. So, if we start new one pointer from start (or move slow or fast to start) and run node by node we will get first cycle node. Super!
Lets implement it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** * Definition for singlylinked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null) return null; ListNode slow = head; ListNode expected = head; ListNode fast = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(expected.equals(slow)) return expected; if(slow.equals(fast)){ expected = expected.next; } } return null; } } /** * Definition for singlylinked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null) return null; ListNode slow = head; ListNode expected = head; ListNode fast = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(expected.equals(slow)) return expected; if(slow.equals(fast)){ expected = expected.next; } } return null; } }


Perfect, both solutions were accepted by leetcode.
Cheers!