Solution: Split a Circular Linked List

Let’s solve the Split a Circular Linked List problem using the Fast and Slow pattern.

We'll cover the following

Statement

Given a circular linked list, list, of positive integers, your task is to split it into two circular linked lists. The first circular linked list should contain the first half of the nodes (exactly ⌈list.length / 2⌉ nodes), in the same order they appeared in the original list, while the second circular linked list should include the remaining nodes in the same order.

Return an array, answer, of length 2, where:

  • answer[0] is the circular linked list representing the first half.

  • answer[1] is the circular linked list representing the second half.

Note: A circular linked list is a standard linked list where the last node points back to the first node.

Constraints:

Let n be the number of nodes in a linked list.

  • 2 ≤\leqn ≤\leq10310^{3}

  • 0≤\leq Node.data ≤\leq10510^{5}

  • LastNode->next = FirstNode where LastNode is the last node of the list and FirstNode is the first one

Solution

The solution utilizes the fast and slow pointers pattern to efficiently split a circular linked list into two halves. This approach helps navigate the circular nature of the list while ensuring the split is done in an optimal number of iterations. By leveraging fast and slow pointers, we can find the midpoint of the list in a single pass and split the list into two circular linked lists.

Now, let’s walk through the steps of the solution:

  1. We initialize the slow and fast pointers to the head of the list. The slow pointer moves one node at a time while the fast pointer moves two nodes at a time.

  2. We iterate through the list using the fast and slow pointers until the fast pointer has reached back to the head, ensured by the conditions fast->next != head and fast->next->next != head.

  3. After iterating, the slow pointer will be at the middle point of the list, while the fast pointer will be pointing back to the head. This middle point node serves as the point where we will split the list into two halves.

  4. The first circular linked list will start from the original head (head1 = head). Before modifying slow->next, we store slow->next in head2 to retain the starting node of the second half. Then, we update slow->next to point back to head1, effectively closing the first circular half.

  5. The second half of the list begins from the node immediately following the middle point, which we stored in head2 in the previous step. This prevents losing the reference to the second half’s start after updating slow->next for the first half.

  6. Next, we need to ensure that the second half is also circular. To do this, we traverse the second half starting from head2 using the fast pointer. The fast moves throughout the list until it points back to the head.

  7. Once the fast pointer reaches the head, we update fast->next=head2, closing the second circular list.

  8. Finally, we return the heads of two split circular linked lists as an array: [head1, head2].

Let’s look at the following illustration to get a better understanding:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.