...

/

Split Linked List into Two Halves

Split Linked List into Two Halves

In this lesson, you will learn how to split a circular linked list into two halves in Python.

We'll cover the following...

In this lesson, we investigate how to split one circular linked list into two separate circular linked lists and then code the solution in Python.

First of all, let’s clarify what we mean by splitting a circular linked list by taking a look at the illustration below.

To approach this problem, we’ll find the length of the circular linked list and calculate the midpoint. Once that is done, we’ll split the linked list around the midpoint. One half will be made by trimming the original linked list while the rest of the elements will be pushed into a new circular linked list.

__len__()

Let’s see how we calculate the length of a circular linked list in Python:

Press + to interact
def __len__(self):
cur = self.head
count = 0
while cur:
count += 1
cur = cur.next
if cur == self.head:
break
return count

Explanation

The __len__ method has been defined with underscores before and after the len keyword so that it overrides the len method to operate on a circular linked list.

Calculating the length of the circular linked list is very straightforward. We declare cur equal to self.head on line 2 to give a start for traversing the circular linked list. count is set to 0 initially on ...