Split Circular List

Problem Statement

Write a Java program that splits a circular linked list into two circular linked lists of roughly equal size. A circular linked list is a singly linked list where the last node’s next pointer points to the head, forming a cycle. The splitting should divide the nodes as evenly as possible, with one list having at most one more node than the other for odd-sized lists, and each resulting list maintaining its circular structure. Test the implementation with even-sized lists, odd-sized lists, empty lists, and single-node lists. You can visualize this as dividing a ring of numbered beads into two smaller rings, each containing about half the beads, with both rings remaining closed loops.

Input:

• A circular linked list of integers (e.g., 1→2→3→4→1, where 4→1 forms the cycle). Output: Two circular linked lists as strings, listing nodes from each head until just before it cycles (e.g., "1 2" and "3 4" for the input above). Constraints:
• The list size is between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• The list may be empty. Example:
• Input: List = 1→2→3→4→1
• Output: First list: "1 2", Second list: "3 4"
• Explanation: Splits into two circular lists of 2 nodes each: 1→2→1 and 3→4→3.
• Input: List = 1→2→3→1
• Output: First list: "1 2", Second list: "3"
• Explanation: Splits into 1→2→1 (2 nodes) and 3→3 (1 node).
• Input: List = []
• Output: First list: "[]", Second list: "[]"
• Explanation: Empty list splits into two empty lists.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION splitList(head)
    IF head is null THEN
        RETURN (null, null)
    ENDIF
    IF head.next is head THEN
        RETURN (head, null)
    ENDIF
    SET length to 1
    SET tail to head
    WHILE tail.next is not head
        INCREMENT length
        SET tail to tail.next
    ENDWHILE
    SET splitPoint to length / 2
    SET current to head
    FOR i from 1 to splitPoint - 1
        SET current to current.next
    ENDFOR
    SET firstHead to head
    SET secondHead to current.next
    SET secondTail to tail
    SET firstTail to current
    SET firstTail.next to firstHead
    SET secondTail.next to secondHead
    RETURN (firstHead, secondHead)
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    SET visited as new Set
    WHILE current is not null AND current not in visited
        ADD current to visited
        APPEND current.value to result
        IF current.next is not head THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of circular linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL splitList(testCase.head)
        PRINT first and second lists using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
2. In splitList: a. If the list is empty, return (null, null). b. If the list has one node, return (head, null). c. Find the list length and tail by traversing until tail.next is head. d. Compute split point as length / 2. e. Traverse to the node before the split point (first list’s tail). f. Set first list’s head and tail, second list’s head and tail. g. Connect first list’s tail to its head, second list’s tail to its head. h. Return (firstHead, secondHead).
3. In toString: a. If head is null, return "[]". b. Traverse from head, use a Set to avoid cycling, append values with spaces. c. Return the string representation.
4. In main, test with even-sized, odd-sized, empty, and single-node circular lists.

Java Implementation

import java.util.*;

public class SplitCircularLinkedList {
    // Node class for the circular linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // Splits the circular linked list into two circular lists
    public Node[] splitList(Node head) {
        Node[] result = new Node[2];
        if (head == null) {
            result[0] = null;
            result[1] = null;
            return result;
        }
        if (head.next == head) {
            result[0] = head;
            result[1] = null;
            return result;
        }
        // Find length and tail
        int length = 1;
        Node tail = head;
        while (tail.next != head) {
            length++;
            tail = tail.next;
        }
        // Find split point
        int splitPoint = length / 2;
        Node current = head;
        for (int i = 0; i < splitPoint - 1; i++) {
            current = current.next;
        }
        // Set heads and tails
        Node firstHead = head;
        Node secondHead = current.next;
        Node firstTail = current;
        Node secondTail = tail;
        // Form two circular lists
        firstTail.next = firstHead;
        secondTail.next = secondHead;
        result[0] = firstHead;
        result[1] = secondHead;
        return result;
    }

    // Converts circular linked list to string
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        Set<Node> visited = new HashSet<>();
        while (current != null && !visited.contains(current)) {
            visited.add(current);
            result.append(current.value);
            if (current.next != head) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;

        TestCase(int[] values) {
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
            // Make circular
            current.next = head;
        }
    }

    // Main method to test circular linked list splitting
    public static void main(String[] args) {
        SplitCircularLinkedList splitter = new SplitCircularLinkedList();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}),     // Even-sized list
            new TestCase(new int[]{1, 2, 3}),        // Odd-sized list
            new TestCase(new int[]{}),               // Empty list
            new TestCase(new int[]{5}),              // Single node
            new TestCase(new int[]{1, 1, 1, 1, 1})   // Odd-sized with duplicates
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + splitter.toString(test.head));
            Node[] result = splitter.splitList(test.head);
            System.out.println("First list: " + splitter.toString(result[0]));
            System.out.println("Second list: " + splitter.toString(result[1]) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4
First list: 1 2
Second list: 3 4

Test case 2:
Input list: 1 2 3
First list: 1 2
Second list: 3

Test case 3:
Input list: []
First list: []
Second list: []

Test case 4:
Input list: 5
First list: 5
Second list: []

Test case 5:
Input list: 1 1 1 1 1
First list: 1 1 1
Second list: 1 1

Explanation:

• Test case 1: Splits 1→2→3→4→1 into 1→2→1 (2 nodes) and 3→4→3 (2 nodes).
• Test case 2: Splits 1→2→3→1 into 1→2→1 (2 nodes) and 3→3 (1 node).
• Test case 3: Empty list splits into "[]" and "[]".
• Test case 4: Single node 5→5 splits into 5→5 and "[]".
• Test case 5: Splits 1→1→1→1→1→1 into 1→1→1→1 (3 nodes) and 1→1→1 (2 nodes).

How It Works

• Node: Stores an integer value and a next pointer.
• splitList:
  • Returns (null, null) for empty lists, (head, null) for single-node lists.
  • Finds list length and tail by traversing to tail.next=head.
  • Computes split point as length / 2.
  • Traverses to the node before the split point (first list’s tail).
  • Sets first list’s head/tail and second list’s head/tail.
  • Connects first tail to first head, second tail to second head.
• toString: Traverses from head, uses a Set to prevent cycling, returns space-separated string or "[]".
• Example Trace (Test case 1):
  • Input: 1→2→3→4→1.
  • length=4, tail=4, splitPoint=2.
  • current=2 (after 1 step), firstHead=1, firstTail=2, secondHead=3, secondTail=4.
  • firstTail.next=firstHead: 1→2→1.
  • secondTail.next=secondHead: 3→4→3.
  • Returns (1, 3), outputs "1 2" and "3 4".
• Main Method: Tests even-sized, odd-sized, empty, single-node, and duplicate lists.

Complexity Analysis Table

Note:

• n is the number of nodes in the list.
• Time complexity: O(n) for splitList (traverse to find length and split point); O(n) for toString (traverse list).
• Space complexity: O(1) for splitList (constant pointers); O(n) for toString (StringBuilder and Set).
• Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Split