Split a circular linked list

Linked List Two Pointers

77.5% acceptance

Mar 31, 2026

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.

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  vector<ListNode*> splitCircularLinkedList(ListNode* list) {
    // Count the length
    int len = 1;
    ListNode* cur = list;
    while (cur->next != list) {
      len++;
      cur = cur->next;
    }
    // cur is now the last node
    int firstHalf = (len + 1) / 2;
    ListNode* node = list;
    for (int i = 1; i < firstHalf; i++) {
      node = node->next;
    }
    // node is the last node of first half
    ListNode* secondHead = node->next;
    node->next = list; // close first circular list
    cur->next = secondHead; // close second circular list
    return {list, secondHead};
  }
};