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:
def __len__(self):cur = self.headcount = 0while cur:count += 1cur = cur.nextif cur == self.head:breakreturn 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 ...