Python Program To Get The Middle Element Of A Linked List In A Single Iteration

Introduction

A linked list is a data structure that is used to store a list of elements. Each element in the linked list is made up of two components. The first component is the data or value that is to be stored, while the second component is a pointer that points to the next element in the linked list. The first element in the linked list is called the head, while the last element is called the tail.

In this article, we will learn how to get the middle element of a linked list in a single iteration using Python programming language.

Solution

In order to get the middle element of a linked list, we can follow the below steps:

1. Create a linked list with some values.
2. Traverse the linked list with two pointers.
3. Move the fast pointer two steps at a time while the slow pointer moves one step at a time.
4. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle element.

Example

Let’s consider the following code snippet to create a linked list in Python.

# Node class to define the structure of each node in the linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Linked List class to create and traverse the linked list
class LinkedList:
    def __init__(self):
        self.head = None

    # Function to add new nodes to the linked list
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Function to find the middle element of the linked list
    def printMiddle(self):
        slow_ptr = self.head
        fast_ptr = self.head

        if self.head is not None:
            while fast_ptr is not None and fast_ptr.next is not None:
                fast_ptr = fast_ptr.next.next
                slow_ptr = slow_ptr.next
            print("The middle element is: ", slow_ptr.data)

# Code to create a linked list and call the printMiddle function
llist = LinkedList()
llist.push(1)
llist.push(2)
llist.push(3)
llist.push(4)
llist.push(5)
llist.printMiddle()

Output:

The middle element is: 3

Explanation

In the above example, we have created a linked list with 5 elements, which are added to the linked list using the push() function.

Then we have implemented the printMiddle() function which finds the middle element of the linked list using two pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle element.

Finally, we have called the printMiddle() function to find the middle element of the linked list, which is printed as output.

Conclusion

In conclusion, getting the middle element of a linked list in a single iteration is a useful task. We can use the above code snippet to implement this functionality in Python programming language. The code is simple to understand and can be easily modified to suit different requirements. Thus, it can be beneficial for programmers who deal with linked lists in their projects.