LinkedListProblem 17 of 36
Split a Circular linked list into two halves
Split a Circular Linked List into Two Halves
Problem Statement
Given a circular linked list, split it into two circular linked lists. If there are odd number of nodes, the first list should have one more node than the second.
Example
Input: 1 -> 2 -> 3 -> 4 -> (back to 1)
Output:
List 1: 1 -> 2 -> (back to 1)
List 2: 3 -> 4 -> (back to 3)
Input: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 1)
Output:
List 1: 1 -> 2 -> 3 -> (back to 1)
List 2: 4 -> 5 -> (back to 4)
Input: 1 -> (back to 1)
Output:
List 1: 1 -> (back to 1)
List 2: null
Brute Force Approach (Count First)
Intuition
Count the total nodes first, then traverse to the appropriate positions to split the list.
Algorithm
- Count total nodes in the circular list
- Calculate split point: mid = (count + 1) / 2
- Traverse to mid position
- Create two circular lists by adjusting pointers
Implementation
Complexity Analysis
- Time Complexity: O(n) - Count + traverse
- Space Complexity: O(1) - Only using pointers
Optimal Approach (Slow-Fast Pointers)
Intuition
Use the slow-fast pointer technique to find the middle without counting. The slow pointer will be at the middle when fast completes the circle.
Algorithm
- Use slow (1 step) and fast (2 steps) pointers
- Stop when fast reaches head or just before head
- Slow will be at middle (end of first half)
- Split at slow and adjust pointers to make both circular
Visualization
Circular list: 1 -> 2 -> 3 -> 4 -> (back to 1)
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=1 (back at head, stop!)
Wait, we need to stop earlier...
Correct approach:
- Start slow at head, fast at head
- Move while fast.next != head AND fast.next.next != head
- This ensures we find the right middle
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass to find middle
- Space Complexity: O(1) - Only using pointers
Visual Walkthrough
Original: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 1)
Using slow-fast pointers:
Initial: slow=1, fast=1
Step 1: slow=2, fast=3
fast.next != head (5 != 1) ✓
fast.next.next != head (4 != 1) ✓
Continue
Step 2: slow=3, fast=5
fast.next == head (1 == 1) ✗
Stop!
Now:
- slow points to 3 (end of first half)
- fast points to 5 (end of second half, before head)
Split:
- head1 = 1 (head)
- head2 = 4 (slow.next)
Make circular:
- slow.next = head1: 3 -> 1 (first list: 1 -> 2 -> 3 -> back to 1)
- fast.next = head2: 5 -> 4 (second list: 4 -> 5 -> back to 4)
Result:
List 1: 1 -> 2 -> 3 -> (back to 1) [3 nodes]
List 2: 4 -> 5 -> (back to 4) [2 nodes]
Helper Function to Display Circular List
Edge Cases
| Case | Input | Output | |------|-------|--------| | Empty | null | (null, null) | | Single node | 1 → (1) | (1 → (1), null) | | Two nodes | 1 → 2 → (1) | (1 → (1), 2 → (2)) | | Odd count | 1→2→3 → (1) | (1→2 → (1), 3 → (3)) |
Key Takeaways
- Slow-fast pointers work for circular lists with modified stopping condition
- The stop condition is
fast.next != head && fast.next.next != head - For odd count, first half gets the extra node
- Both resulting lists must be made circular (update tail.next to head)
- Fast pointer at the end helps avoid another traversal to find the tail
- This is a fundamental operation for circular list manipulation