Check if a linked list is a circular linked list
Check if a Linked List is Circular
Problem Statement
A circular linked list is a linked list where the last node points back to the head (first node), forming a complete circle. Given a linked list, determine if it is circular.
Note: This is different from detecting a cycle - a circular list specifically has the last node pointing to the head.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 1)
Output: true (circular)
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: false (not circular, ends with null)
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (back to 3)
Output: false (has cycle but not circular - doesn't point to head)
Brute Force Approach (Using HashSet)
Intuition
Traverse the list and store visited nodes. If we encounter the head again before reaching null, it's circular.
Algorithm
- If list is empty, return false
- Store head in a set
- Traverse the list
- If we reach null, return false
- If we reach head again, return true
- If we reach any other visited node, return false (cycle but not circular)
Implementation
Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - HashSet stores all nodes
Optimal Approach (Simple Traversal)
Intuition
A simpler approach: Just traverse the list and check if any node's next pointer points to head. If we reach null first, it's not circular.
Algorithm
- If list is empty, return false
- Start from head and traverse
- If any node's next is head, return true
- If we reach null, return false
Implementation
Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(1) - Only using one pointer
Alternative: Using Floyd's Cycle Detection
Intuition
We can use Floyd's algorithm to detect if there's a cycle, and then check if the cycle includes the head.
Implementation
Circular vs Has Cycle
| Property | Circular | Has Cycle | |----------|----------|-----------| | Definition | Last node → Head | Any node → Previous node | | Example | 1→2→3→1 | 1→2→3→2 | | Cycle Start | Always at Head | Can be anywhere | | Detection | Check if any next == head | Floyd's algorithm |
Creating a Circular Linked List
Key Takeaways
- A circular list has its last node pointing to the head
- The simple traversal approach is O(1) space and very clean
- Different from cycle detection - circular means cycle starts at head
- Floyd's algorithm can be adapted but is overkill for this problem
- When creating circular lists, ensure the last node always points to head
- Single node circular list:
head.next = head - This concept is used in round-robin scheduling and buffer implementations