We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split a Circular Linked List

Number: 2835

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a circular linked list of positive integers, split it into two circular linked lists. The first list should contain the first half of the nodes (i.e. ceil(list.length / 2) nodes) in the order they appear, and the second list should contain the remaining nodes in the same order. Each resulting list must also maintain a circular structure.

Key Insights

  • The list is circular; hence, the last node points back to the head.
  • Determine the total number of nodes to identify the splitting point.
  • Use ceil(n/2) to determine how many nodes go into the first half.
  • Traverse the list to locate the node right before the split and adjust the pointers accordingly.
  • Ensure that both resulting linked lists are circular by properly setting the next pointer of each list's last node.
  • Handle edge cases where the list may have a minimal number of nodes.

Space and Time Complexity

Time Complexity: O(n) - traversing the list to count nodes and to perform the split. Space Complexity: O(1) - only constant extra space is used.

Solution

The solution uses a two-phase approach:

  1. First, count the total number of nodes by traversing the circular linked list until returning to the head. Calculate the number of nodes for the first half using ceil(n/2).
  2. Traverse again until reaching the splitting point, then adjust the next pointer of the last node of the first half to point back to the head, forming its circular structure. Similarly, traverse the remaining part to find the tail of the second half and adjust its next pointer to point to the start of the second list. This approach ensures each sub-list maintains its circularity while preserving the original order of nodes.

Code Solutions

# Definition for Node.
# class Node:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def splitCircularLinkedList(head):
    if not head or head.next == head:
        return [head, None]

    # Count number of nodes in the circular linked list.
    count = 1
    current = head.next
    while current != head:
        count += 1
        current = current.next

    # Calculate the number of nodes for the first half (ceil(count/2)).
    splitCount = (count + 1) // 2

    # Traverse to get the last node of the first half.
    first_half_last = head
    for _ in range(splitCount - 1):
        first_half_last = first_half_last.next
    second_head = first_half_last.next

    # Close the first circular linked list.
    first_half_last.next = head

    # Find the tail of the second half to complete its circular linking.
    second_tail = second_head
    while second_tail.next != head:
        second_tail = second_tail.next
    second_tail.next = second_head

    return [head, second_head]

# Example usage:
# Given a helper function to create and print a circular linked list as needed.
← Back to All Questions