Split a Circular Linked List
curriculum variant — split a circular linked list into two roughly equal halves, each itself circular.
Medium
Time
O(n) Space O(1) 4 min read
fast-slow linked-list
Problem#
(curriculum variant — no canonical LeetCode entry.) Given the head of a circular singly linked list, split it into two circular halves and return their heads. If the length is odd, the first half gets the extra node.
Examples#
- Circular
[1 → 2 → 3 → 4 → 5 → 6 → 1]→ first half[1 → 2 → 3 → 1], second[4 → 5 → 6 → 4].
Constraints#
- Length in
[1, 10^5].
Hints#
Hint 1
Standard fast/slow but stop fast on
next == head or next->next == head rather than null — it’s a circular list. Approach#
Modify the cycle-termination predicate from “fast reaches null” to “fast wraps around to head”. After locating the middle, splice the list into two cycles by cutting at the middle and pointing each tail back to its respective head.
Solution#
pair<ListNode*, ListNode*> splitCircular(ListNode* head) { if (!head) return {nullptr, nullptr}; if (head->next == head) return {head, nullptr};
ListNode *slow = head, *fast = head; while (fast->next != head && fast->next->next != head) { slow = slow->next; fast = fast->next->next; } // If even length, fast lands on the last node; if odd, fast->next is last. if (fast->next->next == head) fast = fast->next;
ListNode* head2 = slow->next; slow->next = head; // close first half fast->next = head2; // close second half return {head, head2};}func splitCircular(head *ListNode) (*ListNode, *ListNode) { if head == nil { return nil, nil } if head.Next == head { return head, nil } slow, fast := head, head for fast.Next != head && fast.Next.Next != head { slow = slow.Next fast = fast.Next.Next } // If even length, fast lands on the last node; if odd, fast.Next is last. if fast.Next.Next == head { fast = fast.Next } head2 := slow.Next slow.Next = head // close first half fast.Next = head2 // close second half return head, head2}from typing import Optional, Tuple
class Solution: def splitCircular(self, head: Optional[ListNode]) -> Tuple[Optional[ListNode], Optional[ListNode]]: if not head: return None, None if head.next is head: return head, None slow, fast = head, head while fast.next is not head and fast.next.next is not head: slow = slow.next fast = fast.next.next # If even length, fast lands on the last node; if odd, fast.next is last. if fast.next.next is head: fast = fast.next head2 = slow.next slow.next = head # close first half fast.next = head2 # close second half return head, head2function splitCircular(head) { if (!head) return [null, null]; if (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 even length, fast lands on the last node; if odd, fast.next is last. if (fast.next.next === head) fast = fast.next; const head2 = slow.next; slow.next = head; // close first half fast.next = head2; // close second half return [head, head2];}class Solution { public ListNode[] splitCircular(ListNode head) { if (head == null) return new ListNode[]{null, null}; if (head.next == head) return new ListNode[]{head, null}; ListNode slow = head, fast = head; while (fast.next != head && fast.next.next != head) { slow = slow.next; fast = fast.next.next; } // If even length, fast lands on the last node; if odd, fast.next is last. if (fast.next.next == head) fast = fast.next; ListNode head2 = slow.next; slow.next = head; // close first half fast.next = head2; // close second half return new ListNode[]{head, head2}; }}function splitCircular(head: ListNode | null): [ListNode | null, ListNode | null] { if (!head) return [null, null]; if (head.next === head) return [head, null]; let slow: ListNode = head, fast: ListNode = head; while (fast.next !== head && fast.next!.next !== head) { slow = slow.next!; fast = fast.next!.next!; } // If even length, fast lands on the last node; if odd, fast.next is last. if (fast.next!.next === head) fast = fast.next!; const head2 = slow.next; slow.next = head; // close first half fast.next = head2; // close second half return [head, head2];}Editorial#
Circular fast/slow needs a tweaked termination — null never appears, so we test against head instead. Each loop iteration advances fast two and slow one; the dual condition handles both odd and even lengths in one place. The two next rewrites turn the single cycle into two disjoint cycles in O(1) work.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#