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, 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 head of the circular linked list representing the first half.answer[1]
is the head of 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.value
LastNode.next = FirstNode
whereLastNode
is the last node of the list andFirstNode
is the first one
Solution
The core idea is to use the slow and fast pointer approach, a well-known technique for finding the middle of a linked list in an optimized manner. The slow pointer moves one step at a time, while the fast pointer moves two steps, ensuring that when the fast pointer completes its traversal, the slow pointer will be at the midpoint. Once the middle is found, we break the circular connection at this midpoint, forming two separate lists. The first half starts from the head and extends up to the slow pointer, with its last node pointing back to the head to maintain the circular structure. The second half begins from the next node after the slow pointer and extends to the original last node, which is then linked back to this second half’s new head, ensuring both resulting lists remain circular. Finally, the two newly formed circular linked lists are returned as separate head pointers representing the start of each half.
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.