141.md

141. Linked List Cycle

Description

Given a linked list, determine if it has a cycle in it.

Follow up: can you solve it without using extra space

Thinking Process

1. The easiest way is to use a hash set to store visited nodes. If a node appears twice there must be a cycle
2. An optimized way is to use two pointers p1, p2. p1 travels 1 step at a time, while p2 travels 2 steps at a time. If p1 and p2 meet at some point, there must be a cycle in the list.

Code

Approach 1 (hash set)

public class Solution {
  public boolean hasCycle(ListNode head) {
      Set<ListNode> set = new HashSet();
      while(head != null){
          if(!set.add(head))
              return true;
          head = head.next;
      }
      return false;
  }
}

Approach 2 (two pointers)

public class Solution {
  public boolean hasCycle(ListNode head) {
      ListNode n1 = head;
      ListNode n2 = head;
      while(n1 != null && n2 != null){
          n1 = n1.next;
          n2 = (n2.next != null) ? n2.next.next : null;
          if(n1 == n2 && n1 != null)
              return true;
      }
      return false;
  }
}

Complexity

1. Approach 1 takes O(n) space and O(n) time
2. Approach 2 takes O(1) space and O(n) time