Finding the middle element of linked List in Python

By Abhishek Kumar

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.

Aim  :

   --> Our aim is to find the middle element of a linked list in Python programming. How we can achieve this.

 

Objectives  :

   -->   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.

 

Example  :

    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

 

This can be solved in many ways : 

            Linked list is :  12 -> 13 -> 14 -> 15 ->16

 

   1.   Using extra space :

 

     Procedure :

1. We create an empty list.
2. We traverse to that node where the node.next value is not None.
3. We store all the node values in the empty list.
4. Then we find the middle element of the list and return it.

     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

 

 

   2.   Two Pointer Method : 

 

     Procedure :

1. We use two pointer technique.
2. We create two nodes one is (turtle) will cover one step at a time and the next is (rabbit) will cover two-step at a time.
3. We traverse the rabbit has reached to the end element.
4. Then the node at which the turtle is stoped that exactly the same element is our middle element.
5. This concept is solved by just understanding the given example.

    

     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

 

 

 

     Full Programming Code :

# 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()