What is the time complexity to split a circular linked list into two equal halves?

• A. O(1)
• B. O(log n)
• C. O(n^2)
• D. O(n)

Answer: (D)

Finding the split point around a circular linked list requires walking through the nodes to locate the halfway mark. A linked list doesn’t support direct indexing, so you must step from node to node until you’ve reached n/2 elements from your starting point. This means you perform a linear number of steps relative to the list size, which is proportional to n. Even using a two-pointer approach (slow and fast) to locate the midpoint in a single pass still ends up visiting a number of nodes proportional to n, so the overall time complexity is linear. Constant time would ignore the need to inspect the list, logarithmic time would require random access with indexing that a linked list doesn’t provide, and quadratic time would imply revisiting nodes more than once unnecessarily. Hence, the operation runs in O(n) time.