What is a cycle/loop in the singly-linked list?

A cycle or loop in a singly-linked list occurs when a node in the list points back to a previous node, creating a closed loop. This means that by continuously following the next pointers, you will eventually revisit the same node, rather than reaching the end of the list (which would normally be indicated by a NULL pointer).

Key Points:

1. Definition: A cycle in a linked list exists if there is some node in the list that can be reached again by continuously following the next pointer[2][3][7].
2. Detection Methods:
   • Hashing/Map Approach: Traverse the linked list and store each visited node in a hash table or map. If a node is encountered that is already in the hash table, a cycle is detected[1][5][9].
   • Two Pointers (Floyd’s Cycle Detection Algorithm): Use two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer[4][7][9].

Example:

• Example 1:
  • Input: head = [3,2,0,-4], pos = 1
  • Output: true
  • Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed)[2].
• Example 2:
  • Input: head = [1][2], pos = 0
  • Output: true
  • Explanation: There is a cycle in the linked list, where the tail connects to the 0th node[2].
• Example 3:
  • Input: head = [1], pos = -1
  • Output: false
  • Explanation: There is no cycle in the linked list[2].

Code Examples:

• Using Hashing:
  python Copy

  def has_cycle(head):
      visited = set()
      current = head
      while current:
          if current in visited:
              return True
          visited.add(current)
          current = current.next
      return False

  • **Time ...