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

  • 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(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