LeetCode 2674 - Split a Circular Linked List

LeetCode Problem 2674

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

The problem asks us to take a circular linked list of positive integers and split it into two separate circular linked lists. The first list should contain the first half of the nodes, rounded up (ceil(length / 2)), and the second list should contain the remaining nodes. Importantly, the relative order of nodes must be preserved, and both resulting lists must maintain the circular property where the last node points back to the first node.

The input is a circular linked list, meaning that traversing it from the head will eventually loop back to the head. The constraints specify that the number of nodes can be up to 105, and each node value can be as large as 109. This tells us that the solution must be linear in time and constant in space beyond the output lists to handle large inputs efficiently.

Key edge cases include lists of length 2, where each split will have one node, and lists with an odd number of nodes, where the first list will contain one more node than the second due to the ceiling operation.

Approaches

A brute-force approach would involve iterating through the circular list to count its length, then iterating again to create two new circular lists by copying the nodes. While correct, this approach requires extra memory proportional to the list length to store the new nodes, and iterating twice could be slightly inefficient.

The optimal approach uses the two-pointer technique to find the split point in a single traversal. We first determine the total number of nodes by traversing the circular list once. Then, we calculate the number of nodes in the first half (ceil(length / 2)) and directly adjust the next pointers to create two circular linked lists without duplicating nodes. This approach runs in linear time and constant additional space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverse twice and create new nodes
Optimal	O(n)	O(1)	Single traversal, split by adjusting pointers

Algorithm Walkthrough

1. Edge Case Check: If the input list is empty or has only one node, return it as the first list and None as the second.
2. Count Total Nodes: Traverse the circular linked list starting from head until we return to head to determine length.
3. Determine First Half Size: Calculate first_half_size = ceil(length / 2).
4. Traverse to Split Point: Starting from head, move first_half_size - 1 steps to reach the last node of the first half.
5. Split the List:

• Let first_tail be the last node of the first half. Its next will point to the head of the second half.
• Let second_head be first_tail.next.
• Update first_tail.next to head to maintain the circular property for the first list.

6. Complete Second List: Traverse from second_head to the original tail node (last node before returning to head) and set its next to second_head.
7. Return Result: Return [head, second_head] as the two circular linked lists.

Why it works: By counting nodes and adjusting pointers instead of copying, we preserve the circular nature and original order. The ceiling operation ensures the first list gets one extra node if the length is odd, which matches the problem requirement.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional, List
import math

class Solution:
    def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:
        if not head or head.next == head:
            return [head, None]

        # Step 1: Count the total number of nodes
        length = 1
        current = head.next
        while current != head:
            length += 1
            current = current.next

        # Step 2: Determine size of the first half
        first_half_size = math.ceil(length / 2)

        # Step 3: Traverse to the last node of the first half
        first_tail = head
        for _ in range(first_half_size - 1):
            first_tail = first_tail.next

        # Step 4: Split the list
        second_head = first_tail.next
        first_tail.next = head

        # Step 5: Complete the second circular list
        current = second_head
        while current.next != head:
            current = current.next
        current.next = second_head

        return [head, second_head]

Implementation Explanation: We first handle the trivial edge case where the list is empty or has one node. Counting nodes allows us to determine the split point accurately. Adjusting the next pointers of the tail nodes preserves the circular structure. This avoids extra memory allocation and preserves original node order.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func splitCircularLinkedList(head *ListNode) []*ListNode {
    if head == nil || head.Next == head {
        return []*ListNode{head, nil}
    }

    // Step 1: Count total nodes
    length := 1
    current := head.Next
    for current != head {
        length++
        current = current.Next
    }

    // Step 2: Determine first half size
    firstHalfSize := (length + 1) / 2

    // Step 3: Traverse to last node of first half
    firstTail := head
    for i := 0; i < firstHalfSize-1; i++ {
        firstTail = firstTail.Next
    }

    // Step 4: Split the list
    secondHead := firstTail.Next
    firstTail.Next = head

    // Step 5: Complete second circular list
    current = secondHead
    for current.Next != head {
        current = current.Next
    }
    current.Next = secondHead

    return []*ListNode{head, secondHead}
}

Go-specific Notes: Go requires explicit nil checks and integer division. We use (length + 1) / 2 to compute the ceiling division without using a math library. The *ListNode type handles pointers directly, so we modify the nodes in place.

Worked Examples

Example 1: nums = [1,5,7]

1. Count nodes: 3
2. First half size: ceil(3 / 2) = 2
3. Traverse 1 step from head (1) → first_tail = 5
4. second_head = 7
5. Update pointers: first_tail.next = 1, last node (7).next = 7
6. Result: [[1,5],[7]]

Example 2: nums = [2,6,1,5]

1. Count nodes: 4
2. First half size: ceil(4 / 2) = 2
3. Traverse 1 step from head (2) → first_tail = 6
4. second_head = 1
5. Update pointers: first_tail.next = 2, last node (5).next = 1
6. Result: [[2,6],[1,5]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the list twice: once for counting, once for splitting. Each node is visited a constant number of times.
Space	O(1)	We only store pointers to nodes; no extra data structures proportional to n are used.

The linear time complexity is optimal since every node must be visited at least once, and constant space is ideal because we are allowed to modify pointers in place.

Test Cases

# Example test cases
assert Solution().splitCircularLinkedList(None) == [None, None]  # empty list
assert Solution().splitCircularLinkedList(ListNode(1, None)) == [ListNode(1), None]  # single node

# Provided examples
head1 = ListNode(1, None)
head1.next = ListNode(5, None)
head1.next.next = ListNode(7, head1)
res1 = Solution().splitCircularLinkedList(head1)
assert [res1[0].val, res1[0].next.val] == [1,5]  # first list
assert res1[0].next.next == res1[0]  # circular check
assert [res1[1].val] == [7]  # second list
assert res1[1].next == res1[1]  # circular check

head2 = ListNode(2)
head2.next = ListNode(6)
head2.next.next = ListNode(1)
head2.next.next.next = ListNode(5, head2)
res2 = Solution().splitCircularLinkedList(head2)
assert [res2[0].val, res2[0].next.val] == [2,6]
assert res2[0].next.next == res2[0]
assert [res2[1].val, res2[1].next.val] == [1,5]
assert res2