Python Program to Find the Middle Element of a Linked List in One Pass

A linked list stores data in non-contiguous memory locations. Nodes containing data items are linked using pointers. Each node contains two fields. The first field stores the data, and the second field contains a link to the next node.

Brute Force Technique

To find the middle element of a linked list, find the length of the linked list by iterating through it until it reaches NULL, then divide the length by 2 to find the index of the middle element. After obtaining the index of the middle element, iterate through the linked list again from the beginning, stopping when you reach the desired index. The data item at that index provides the middle element.

• Create a variable called “temp” that points to the beginning of the list and initialize “len” to 0.

• Use temp to iterate through the linked list until it reaches NULL, increasing “len” by 1 each time you reach a node.

• After obtaining the length of the linked list, reinitialize temp to the head. Iterate the linked list until len // 2.

Using Slow and Fast Pointers (Single Iteration)

We will use two pointers to traverse the linked list. One is called the “slow pointer” and the other is called the “fast pointer.”

The “fast pointer” will move at double the speed.

When the fast pointer reaches the end of the linked list, the “slow pointer” will be at the middle node.

Therefore, we can directly print the contents of the middle node.

Example

Consider the following linked list. The middle element is 3.

The fast pointer has reached the last node in the linked list, and the slow pointer now points to node 3. Therefore, 3 is the middle element of the given linked list. Now consider 6 nodes.

Example

The fast pointer has reached NULL, and the slow pointer points to the fourth node. Therefore, the middle element is 4.

Algorithm

• Make “slow” and “fast” point to the head of the linked list.

• Increment the fast pointer and the slow pointer by 1 in the following manner until the fast pointer and **fast.next** are not equal to NULL.

• Print the value at the slow pointer.

• The time complexity is O(n).

class Node:
  def __init__(self, val):
      self.val = val
      self.next = None
class LinkedList:
  def __init__(self):
      self.head = None

  def insert_at_the_beginning(self, newVal):
      newNode = Node(newVal)
      newNode.next = self.head
      self.head = newNode
  def print_middle_element(self):
      slow=self.head
      fast=self.head
      while fast is not None and fast.next is not None:
          slow=slow.next #slow pointer moves one node
          fast=fast.next.next #fast pointer moves two nodes
      print("nnthe middle element is ",slow.val)
  def Print_the_LL(self):
      temp = self.head
      if(temp != None):
        print("The linked list elements are:", end=" ")
        while (temp != None):
          print(temp.val, end=" ")
          temp = temp.next
      else:
        print("The list is empty.")
newList = LinkedList()
newList.insert_at_the_beginning(5)
newList.insert_at_the_beginning(4)
newList.insert_at_the_beginning(3)
newList.insert_at_the_beginning(2)
newList.insert_at_the_beginning(1)
newList.Print_the_LL()
newList.print_middle_element()

Output

The linked list elements are: 1 2 3 4 5

the middle element is 3