Split a circular linked list into two halves

Medium

Problem

Split a circular linked list into two circular lists of equal size. If the length is odd, the first list gets one extra node.

Example 1

Input:  1 → 2 → 3 → 4 → 5 → (1)
Output: 1 → 2 → 3 → (1) and 4 → 5 → (4)

Also asked as: Split a Circular linked list into two halves

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Fast/slow to find the split, then close both loops

Time O(n)Space O(1)

Advance slow by 1 and fast by 2 around the circle; slow ends at the end of the first half. Point each half’s tail back to its own head.

function splitCircular(head) {
if (!head || head.next === head) return [head, null];
let slow = head, fast = head;
while (fast.next !== head && fast.next.next !== head) { slow = slow.next; fast = fast.next.next; }
if (fast.next.next === head) fast = fast.next; // even length
const head2 = slow.next;
slow.next = head; // close first half
fast.next = head2; // close second half
return [head, head2];
}