Split a Circular Linked List

Problem

Given a circular linked list list of positive integers, your task is to split it into 2 circular linked lists so that the first one contains the first half of the nodes in list (exactly ceil(list.length / 2) nodes) in the same order they appeared in list, and the second one contains the rest of the nodes in list in the same order they appeared in list.

Return an array answer of length 2 in which the first element is acircular linked list representing the first half and the second element is a circular linked list representing the second half.

A circular linked list is a normal linked list with the only difference being that the last node’s next node, is the first node.

Examples

Example 1:

1
2
3


Input: nums = [1,5,7]
Output: [[1,5],[7]]
Explanation: The initial list has 3 nodes so the first half would be the first 2 elements since ceil(3 / 2) = 2 and the rest which is 1 node is in the second half.

Example 2:

1
2
3


Input: nums = [2,6,1,5]
Output: [[2,6],[1,5]]
Explanation: The initial list has 4 nodes so the first half would be the first 2 elements since ceil(4 / 2) = 2 and the rest which is 2 nodes are in the second half.

Constraints:

The number of nodes in list is in the range [2, 10^5]
0 <= Node.val <= 10^9
LastNode.next = FirstNode where LastNode is the last node of the list and FirstNode is the first one

Solution

Method 1 – Two Pointers (Fast and Slow)

Intuition

To split a circular linked list into two halves, we can use the classic fast and slow pointer approach to find the midpoint. This allows us to determine where to break the list, and then we can adjust the next pointers to form two new circular lists.

Approach

Use two pointers, slow and fast, to find the midpoint of the circular list.
Move fast by two steps and slow by one step until fast reaches the end.
The node after slow is the start of the second half.
Break the list into two by updating the next pointers so that both halves are circular.
Return the heads of the two new lists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    vector<Node*> splitList(Node* head) {
        if (!head || head->next == head) return {head, nullptr};
        Node* slow = head, *fast = head;
        while (fast->next != head && fast->next->next != head) {
            slow = slow->next;
            fast = fast->next->next;
        }
        Node* head2 = slow->next;
        slow->next = head;
        Node* curr = head2;
        while (curr->next != head) curr = curr->next;
        curr->next = head2;
        return {head, head2};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    public Node[] splitList(Node head) {
        if (head == null || head.next == head) return new Node[]{head, null};
        Node slow = head, fast = head;
        while (fast.next != head && fast.next.next != head) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node head2 = slow.next;
        slow.next = head;
        Node curr = head2;
        while (curr.next != head) curr = curr.next;
        curr.next = head2;
        return new Node[]{head, head2};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def splitList(self, head: 'Node') -> list['Node']:
        if not head or head.next == head:
            return [head, None]
        slow, fast = head, head
        while fast.next != head and fast.next.next != head:
            slow = slow.next
            fast = fast.next.next
        head2 = slow.next
        slow.next = head
        curr = head2
        while curr.next != head:
            curr = curr.next
        curr.next = head2
        return [head, head2]

Complexity

⏰ Time complexity: O(n), where n is the number of nodes, as we traverse the list once.
🧺 Space complexity: O(1), only pointers are used.

Problem#

Examples#

Solution#

Method 1 – Two Pointers (Fast and Slow)#

Intuition#

Approach#

Code#

Complexity#