Find the Middle element of Linked List in Python
In this tutorial, we will learn how to find the middle element of a linked list in Python.
Linked is a linear data structure. Each element consist of two items first being the data and the second being the reference to the next node item. The first node of the linked list is called as the head node. As compared to arrays linked lists are the better option for performing operations such as insertion and deletion, whereas arrays are good for accessing random elements of the arrays. These were the few things you needed to know before beginning with the linked list. In this tutorial, we are going to learn how to find the middle element of linked list in O(n).
Approaches to find the middle element of a Linked List:
- Counting the number of elements in the linked list and then dividing by 2 to locate the middle element. This is what is known as the naive solution.
- A better and effective way is to initialize two-variables and increase one of them by 1 and others by 2. So by the time, the latter one’s points to the null the other would have been at the center/middle.
The code to the second approach is given below but I highly recommend to try the approach first on your IDE first before looking at the code below.
Python program to find the middle element of a Linked List
class Node: def __init__(self,data): self.data=data self.next=None class Linked_List: def __init__(self): self.head=None self.root=None def print(self): temp=self.root while(temp): print(temp.data) temp=temp.next def push(self,data): new=Node(data) if(self.head==None): self.head=new self.root=new else: self.head.next=new self.head=new def middle(self): i1=i2=self.root if(i1 is not None): while(i1 is not None and i1.next is not None): i1=i1.next.next i2=i2.next print("Middle is: ",i2.data) if __name__=="__main__": llist=Linked_List() llist.push(1) llist.push(2) llist.push(3) llist.push(4) llist.push(5) llist.push(6) llist.push(7) llist.push(8) llist.push(9) llist.push(10) llist.middle()
Output Middle is: 6
The class Node above is to initialize the node objects. Approach 2 is implemented in the function middle() of the Linked_List class. You can also use user input using the input() method. Instead of giving the inputs by yourself in the push method. list is the object of class Linked_List.
The code complexity for this approach is O(n), where n is the number of elements in the linked list.
[Note: In case of even elements in the list the later of middle 2 elements is called the middle. You can consider this to be a world convention.]