In this Python source code, we use two methods to solve this problem, one by using extra space and the other by the two-pointer method.
--> Our aim is to find the middle element of a linked list in Python programming. How we can achieve this.
--> Our prime focus is to find the middle element of the linked list, not how to
implement the linked list.
--> We are working on a singly linked list.
--> But we can use these methods to find the middle element in any type of linked list.
1. If the length of the linked list is odd:
23 -> 12 -> 45 -> 76 -> 84
Middle element is : 45
2. If the length of the linked list is even:
46 -> 113 -> 614 -> 195 -> 116 ->167
Middle element is : 195
Linked list is : 12 -> 13 -> 14 -> 15 ->16
Procedure :
Code :
# This is the main programming code for finding the middle element of the linked list.
# If you want full code then download the zip file.
def Store_in_list(self):
# we create an empty list to store all the data present in the linked List. data1=[]
# We create a veriable which help us to find the current node. n=self.head
# We run a while loop with stopping condition that the variable 'n'is not None. while n is not None:
# We start appending the value in the empty list . data1.append(n.data)
# And always changing the pointer to next node till the condition become false. n=n.next
# And then find the middle element and print it. print(“The Middle Element is : “,data1[len(data1)//2)])
OUTPUT : The Middle Element is : 14
Procedure :
Example :
Itteration 1 :
12 - > 13 - > 14 - > 15 - > 16
[Turtle]
[Rabbit]
Itteration 2 :
12 - > 13 - > 14 - > 15 - > 16
[Turtle]
[Rabbit]
Itteration 3 :
12 - > 13 - > 14 - > 15 - > 16
[Turtle]
[Rabbit]
Itteration 4 :
12 - > 13 - > 14 - > 15 - > 16
1. The rabbit will not go further as it reaches the end.
2. As I say the previous Turtle is in the middle Of the linked list. Which is our desired result.
Code :
# This is the main programming code for finding the middle element of the linked list.
# If you want full code then download the zip file.
def printMiddle(self):
# Turtle pointer will move only one step at a time. Turtle = self.head
# Rabbit pointer will move two steps at a time. Rabbit = self.head
# We traverse the linked list till the stopping condition.
# ie. poinnter Turtle and Rabbit.next is not none. while Turtle and Rabbit.next: Turtle = Turtle.next Rabbit = Rabbit.next.next
# when the while loop terminate the Turtle pointer node is our desired result. print("The middle element is : ",Turtle.data)
OUTPUT : The Middle Element is : 14
# Our prime focous is to find the middle element of the linked list.
# Not in the complete development of the linked list.
# We crete a node which has two part. One will store Data and
# other will store Adress of the next node Initially it is None.
class Node: def __init__(self,data): self.data=data self.next=None
# Now we are going to implement the linked list. class LinkedList:
# We define a constructor which help us to create the head pointer of the
# Singly linked list. def __init__(self): self.head=None # We add only the node in the beginning, So we define a method which take
# data as a parameter. def add_beg(self,data):
# We firstly create a newNode by just calling the Node class. newNode=Node(data)
# Firstly we update the newNode adress part. newNode.next=self.head
# Then we Update the head of the linked list. self.head=newNode def Store_in_list(self):
# we create an empty list to store all the data present in the linked List.
data1=[]
# We create a veriable which help us to find the current node.
n=self.head
# We run a while loop with stopping condition that the variable 'n'is not None.
while n is not None:
# We start appending the value in the empty list .
data1.append(n.data)
# And always changing the pointer to next node till the condition become false.
n=n.next def printMiddle(self):
# Turtle pointer will move only one step at a time.
Turtle = self.head
# Rabbit pointer will move two steps at a time.
Rabbit = self.head
# We traverse the linked list till the stopping condition.
# ie. poinnter Turtle and Rabbit.next is not none.
while Turtle and Rabbit.next:
# Turtle pointer wil move only one step in a single itteration.
Turtle = Turtle.next
# Rabbit pointer will move two steps in a single itteration.
Rabbit = Rabbit.next.next
# when the while loop terminate the Turtle pointer node is our desired result.
print("The middle element is : ",Turtle.data)
# We create a object n1. n1=LinkedList()
# Then we add few element. n1.add_beg(11) n1.add_beg(12) n1.add_beg(13
# We print the middle element of the list. print(data1[len(data1)//2]))
# We call the two Pointer function to find middle element. n1.printMiddle()
Submitted by Abhishek Kumar (kumarabhishek03)
Download packets of source code on Coders Packet
Comments