Split a Circular Linked List - Practice Coding Problems

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 a circular 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.

Input & Output

Example 1 — Odd Number of Nodes

$ Input: head = [1,2,3,4,5]

› Output: [[1,2,3],[4,5]]

💡 Note: The list has 5 nodes. First half gets ceil(5/2) = 3 nodes: [1,2,3]. Second half gets remaining 2 nodes: [4,5]. Both halves are made circular.

Example 2 — Even Number of Nodes

$ Input: head = [1,2,3,4]

› Output: [[1,2],[3,4]]

💡 Note: The list has 4 nodes. First half gets ceil(4/2) = 2 nodes: [1,2]. Second half gets remaining 2 nodes: [3,4]. Both are circular.

Example 3 — Single Node

$ Input: head = [1]

› Output: [[1],[]]

💡 Note: Only one node, so first half contains [1] and second half is empty. The single node points to itself.

Constraints

1 ≤ list.length ≤ 10⁵
1 ≤ list[i] ≤ 10⁶
The input list is a circular linked list

Visualization

Tap to expand

Understanding the Visualization

Input

Circular linked list [1,2,3,4,5] where 5 points back to 1

Find Split Point

Use two-pointer technique or count nodes to find middle

Output

Two circular lists: [1,2,3] and [4,5]

Key Takeaway

🎯 Key Insight: Use fast-slow pointers to find the split point in one traversal

Asked in

M Microsoft 15 a Amazon 12 f Facebook 8

Split a circular linked list into two halves efficiently. The key insight is using fast-slow pointers to find the middle in one pass. Best approach is two-pointer technique with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass Approach	O(n)	O(1)	Count nodes first, then traverse again to split
Fast-Slow Pointer Optimized	O(n)	O(1)	Use fast and slow pointers to find middle in one pass

Two Pass Approach — Algorithm Steps

Step 1: Traverse once to count total nodes
Step 2: Calculate split point (ceil(n/2))
Step 3: Traverse again to split point and break connections
Step 4: Make both parts circular

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Nodes

Traverse the circular list to count total nodes

Calculate Split

Find split position: ceil(count/2)

Split & Make Circular

Break at split point and make both parts circular

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode** solution(struct ListNode* head) {
    struct ListNode** result = (struct ListNode**)malloc(2 * sizeof(struct ListNode*));
    
    if (!head) {
        result[0] = NULL;
        result[1] = NULL;
        return result;
    }
    
    // First pass: count nodes
    int count = 1;
    struct ListNode* current = head->next;
    while (current != head) {
        count++;
        current = current->next;
    }
    
    // Calculate split point
    int firstHalfSize = (count + 1) / 2;
    
    // Second pass: find split point
    current = head;
    for (int i = 0; i < firstHalfSize - 1; i++) {
        current = current->next;
    }
    
    // Split the list
    struct ListNode* secondHead = current->next;
    current->next = head; // Make first half circular
    
    // Find end of second half and make it circular
    if (secondHead != head) {
        struct ListNode* secondCurrent = secondHead;
        while (secondCurrent->next != head) {
            secondCurrent = secondCurrent->next;
        }
        secondCurrent->next = secondHead;
        result[0] = head;
        result[1] = secondHead;
    } else {
        result[0] = head;
        result[1] = NULL;
    }
    
    return result;
}

struct ListNode* buildList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = createNode(arr[0]);
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(arr[i]);
        current = current->next;
    }
    current->next = head;
    return head;
}

void printList(struct ListNode* head) {
    if (!head) {
        printf("[]");
        return;
    }
    printf("[");
    struct ListNode* current = head;
    int first = 1;
    do {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    } while (current != head);
    printf("]");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = buildList(arr, size);
    struct ListNode** result = solution(head);
    
    printf("[");
    printList(result[0]);
    printf(",");
    printList(result[1]);
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the circular list, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler