Skip to main content
Talentd

Split a Circular Linked List - Solution & Explanation

MediumPremiumFree on FleetCodeLinked ListTwo Pointers8 min read
Practice this problem

Problem Statement

Given a circular linked list list of positive integers, your task is to split it into 2 circular linked lists so that the first one contains the first half of the nodes in list (exactly ceil(list.length / 2) nodes) in the same order they appeared in list, and the second one contains the rest of the nodes in list in the same order they appeared in list.

Return an array answer of length 2 in which the first element is a circular linked list representing the first half and the second element is a circular linked list representing the second half.

A circular linked list is a normal linked list with the only difference being that the last node's next node, is the first node.

 

Example 1:

Input: nums = [1,5,7]
Output: [[1,5],[7]]
Explanation: The initial list has 3 nodes so the first half would be the first 2 elements since ceil(3 / 2) = 2 and the rest which is 1 node is in the second half.

Example 2:

Input: nums = [2,6,1,5]
Output: [[2,6],[1,5]]
Explanation: The initial list has 4 nodes so the first half would be the first 2 elements since ceil(4 / 2) = 2 and the rest which is 2 nodes are in the second half.

 

Constraints:

  • The number of nodes in list is in the range [2, 105]
  • 0 <= Node.val <= 109
  • LastNode.next = FirstNode where LastNode is the last node of the list and FirstNode is the first one

Approach Overview

Problem Overview: You receive the head of a circular linked list and must split it into two separate circular linked lists. The first half should contain the extra node when the length is odd. Both resulting lists must remain circular and preserve the original order of nodes.

Approach 1: Count Nodes Then Split (O(n) time, O(1) space)

The direct method first determines the total number of nodes in the circular list. Start at head and iterate until you reach the head again, counting nodes along the way. Once the length n is known, compute the midpoint (n + 1) / 2 so the first list gets the extra node when the size is odd.

Traverse again until you reach the midpoint node. Break the list by updating pointers: the midpoint becomes the tail of the first circular list, and the last node becomes the tail of the second circular list. Each tail must point back to its respective head. This approach is easy to reason about and useful when you want explicit control over positions in a linked list, but it requires two full traversals.

Approach 2: Fast and Slow Pointers (O(n) time, O(1) space)

The optimal method uses the classic two pointers technique. Initialize slow and fast at the head. Move slow one step and fast two steps at a time. Stop when fast reaches the end of the circular traversal (either fast.next == head or fast.next.next == head).

At that moment, slow points to the midpoint of the list. The node after slow becomes the head of the second circular list. Adjust pointers carefully: set slow.next to the original head to close the first circle, and connect the last node (tracked by fast) to the second head to close the second circle.

This works because the fast pointer covers twice the distance of the slow pointer, naturally landing the slow pointer at the midpoint. The algorithm performs only one traversal and does not require additional memory, making it the preferred solution for most linked list interview problems.

Recommended for interviews: The fast and slow pointer approach is what interviewers expect. It demonstrates mastery of pointer movement patterns and efficient traversal of circular structures. The counting approach still shows you understand pointer manipulation, but the two-pointer method highlights stronger algorithmic thinking and optimal single-pass design.

Solution

We define two pointers a and b, both initially pointing to the head of the linked list. Each iteration, pointer a moves forward one step, and pointer b moves forward two steps, until pointer b reaches the end of the linked list. At this point, pointer a points to half of the linked list nodes, and we break the linked list from pointer a, thus obtaining the head nodes of the two linked lists.

The time complexity is O(n), where n is the length of the linked list. It requires one traversal of the linked list. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count Nodes Then SplitO(n)O(1)When clarity is preferred and two passes over the list are acceptable
Fast and Slow PointersO(n)O(1)Preferred interview solution; single traversal using two-pointer technique

Video Solution

Leetcode 2674 Split a Circular Linked List • AlgorithmicIQ • 32 views views

Frequently Asked Questions

Is Split a Circular Linked List easy or hard?
The problem is typically classified as Medium difficulty. Pointer manipulation in a circular structure can be tricky, especially handling edge cases with odd lengths or very small lists.
Split a Circular Linked List Python/Java solution
Most implementations follow the same logic across languages. Use two pointers to locate the midpoint, then update pointers so the first half ends at the slow pointer and the second half begins at slow.next, with both tails pointing to their respective heads.
How to solve Split a Circular Linked List in O(n)?
Use two pointers starting at the head. Move the fast pointer two steps and the slow pointer one step until the fast pointer reaches the last or second-to-last node of the circular list. The slow pointer marks the midpoint, after which pointer updates create two separate circular linked lists.
What is the best approach for Split a Circular Linked List?
The fast and slow pointer technique is the best approach. Move a slow pointer one step and a fast pointer two steps until the fast pointer reaches the end of the circular traversal. The slow pointer lands at the midpoint, allowing you to split the list into two circular halves in O(n) time and O(1) space.
Is Split a Circular Linked List asked at Google/Amazon/Meta?
Variants of linked list splitting and fast–slow pointer problems appear in interviews at companies like Amazon, Google, and Meta. While the exact circular version is less common, the underlying pattern—finding the midpoint of a linked list and adjusting pointers—is frequently tested.
What data structure is used in Split a Circular Linked List?
The problem uses a circular singly linked list. Nodes are connected so that the last node points back to the head instead of null, forming a cycle that requires careful traversal and pointer updates during the split operation.
What is the time complexity of Split a Circular Linked List?
The optimal solution runs in O(n) time because each node is visited at most once during the fast–slow traversal. Space complexity is O(1) since the algorithm only uses a few pointer variables and does not allocate extra data structures.

Ready to solve this problem?

Practice Split a Circular Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Split Linked List in Parts