252. Split a Circular Linked List Into Two Halves

A circular singly linked list has n node values (its last node's next pointer points back to the first node). Split it into two circular linked lists of roughly equal size: the first half gets ceil(n/2) nodes and the second half gets the rest, both taken from the front in original order. Print the first half's values on one line and the second half's values on the next line.

Input: The first line contains an integer n. The second line contains n space-separated integers, the circular linked list's values in original order. Output: Print the first half's values on one line and the second half's values on the next line.

2 <= n <= 10^5

Detecting when the FAST pointer has looped back to the head (rather than hitting null, as in a normal list) is the one adaptation needed to apply the familiar slow/fast technique to a CIRCULAR list.

Split a circular linked list into two roughly equal-sized circular linked lists. Brute force: Walk the entire circular list once first to count its total length, then walk it again to find the exact midpoint by index - this works but requires TWO passes, when the slow/fast technique finds the split point in just one. Optimised: The slow/fast pointer technique (adapted for a circular list, watching for the fast pointer to return to the head rather than hitting null) finds the split point in a single pass, exactly like finding the middle of a normal linear list - the only extra care needed is properly re-closing BOTH halves into their own valid circles afterward.

First traverse the circular list once, counting nodes until the traversal returns to the head, giving the total count n; compute k = ceil(n/2). Then traverse the list a second time, walking k-1 steps from the head to reach the node that ends the first half, and relink pointers there: the first half's last node points back to the original head (closing its own circle), and the second half's last node (found by continuing the original traversal back to just before the head) points back to the node right after the split point. Print both halves' values from these two now-independent circular lists. This needs two separate passes but no extra array of values. Time: O(n) (two passes) Space: O(1) extra

Traverse the circular list once starting from the head, stopping as soon as the next pointer returns to the head, collecting all n values into an array along the way. Compute k = ceil(n/2), then simply print the first k values as the first half and the remaining values as the second half directly from the array, without needing to reconstruct any actual linked structure. This is easy to get right but spends extra memory holding a full copy of the list's values. Time: O(n) Space: O(n)

Use the classic tortoise-and-hare technique in one traversal: a slow pointer advances one node at a time while a fast pointer advances two nodes at a time, both starting at the head; because the list is circular, the fast pointer (or fast pointer's next) returning to the head signals that slow has simultaneously reached the split point, with a small adjustment (advancing slow one extra step) to correctly land on ceil(n/2) when n is odd. As soon as slow reaches the split point, the same relinking as before is performed immediately, avoiding the separate counting pass entirely. Time: O(n) (single pass) Space: O(1) extra

1. Use the slow/fast pointer technique to find the split point in a single pass, since the list's exact length isn't given as a direct count. 2. Once found, make the FIRST half's last node point back to the first half's own first node (closing it into its own circle). 3. Do the same for the second half, making ITS last node point back to ITS own first node.

Time: O(n) - a single pass using slow/fast pointers to find the split point. Space: O(1) extra space - just pointers, relinking existing nodes.

n = 2 (minimum size, one node per half), odd n (the extra node goes to the first half), and n = 10^5 for performance.

Be ready to state the exact tie-breaking rule for odd-length lists (the extra node goes to the FIRST half, per this problem's specific convention) - different problems sometimes make the opposite choice, so always confirm.