Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/141.html

141	Linked List Cycle

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

Follow up:
Can you solve it without using extra space?

@tag-linkedlist

Algorithm

Two pointers, a slow pointer that walks one step at a time and a fast pointer that walks two steps at a time. If there is a ring in the linked list, the two pointers will definitely meet at the same position eventually.

Or, use a set for duplicate check.

Code

• Java
• C++
• Python

• import java.util.HashSet;
  import java.util.Set;
  
  public class Linked_List_Cycle {
  
  	/**
  	 * Definition for singly-linked 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 == fast) return true;
              }
  
              return false;
          }
      }
  
  	public class Solution_extra_space {
  	    public boolean hasCycle(ListNode head) {
  
  	        Set<ListNode> hs = new HashSet<ListNode>();
  
  	        ListNode current = head;
  
  	        while (current != null) {
  
  	            if (hs.contains(current)) {
  	                return true;
  	            }
  
  	            hs.add(current);
  	            current = current.next;
  	        }
  
  	        return false;
  
  	    }
  	}
  
  }
  

• // OJ: https://leetcode.com/problems/linked-list-cycle/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      bool hasCycle(ListNode *head) {
          ListNode *p = head, *q = head;
          while (q && q->next) {
              p = p->next;
              q = q->next->next;
              if (p == q) return true;
          }
          return false;
      }
  };
  

• # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  
  class Solution:
      def hasCycle(self, head: ListNode) -> bool:
          slow = fast = head
          while fast and fast.next:
              slow, fast = slow.next, fast.next.next
              if slow == fast:
                  return True
          return False
  
  ############
  
  # Definition for singly-linked list.
  # class ListNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution(object):
    def hasCycle(self, head):
      """
      :type head: ListNode
      :rtype: bool
      """
      fast = slow = head
      while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if slow == fast:
          return True
      return False
  
  

All Problems

All Solutions