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
n
0
Node.data
LastNode->next = FirstNode
whereLastNode
is the last node of the list andFirstNode
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:
We initialize the
slow
andfast
pointers to thehead
of the list. Theslow
pointer moves one node at a time while thefast
pointer moves two nodes at a time.We iterate through the list using the
fast
andslow
pointers until thefast
pointer has reached back to thehead
, ensured by the conditionsfast->next != head
andfast->next->next != head
.After iterating, the
slow
pointer will be at the middle point of the list, while thefast
pointer will be pointing back to thehead
. This middle point node serves as the point where we will split the list into two halves.The first circular linked list will start from the original head (
head1 = head
). Before modifyingslow->next
, we storeslow->next
inhead2
to retain the starting node of the second half. Then, we updateslow->next
to point back tohead1
, effectively closing the first circular half.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 updatingslow->next
for the first half.Next, we need to ensure that the second half is also circular. To do this, we traverse the second half starting from
head2
using thefast
pointer. Thefast
moves throughout the list until it points back to thehead
.Once the
fast
pointer reaches thehead
, we updatefast->next=head2
, closing the second circular list.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 70+ hands-on prep courses.