middle element of linked list Algorithm
The middle element of a linked list algorithm is a popular problem in computer science where the task is to find the center value of a singly-linked list. In a singly-linked list, each node contains a data field and a reference to the next node in the list. The middle element is the one that is located exactly in the center of the list, or as close to the center as possible in the case of an even number of elements. This algorithm is often used as a means of practice for traversing linked lists, and it can be utilized in various applications, such as finding the median value in a data set or splitting a list into two equal parts.
There are several approaches to finding the middle element of a linked list, with the most common one being the "slow and fast pointer" technique. This involves initializing two pointers at the head of the list, with one pointer (the slow pointer) moving one step at a time, and the other pointer (the fast pointer) moving two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element. This method has a time complexity of O(n), as it requires traversing the linked list only once. Other approaches include using an array to store the elements and then finding the middle index, or traversing the list twice, first to count the number of elements and then to locate the middle element. However, these methods may increase the time complexity or require additional memory space.
class Node:
def __init__(self, data: int) -> int:
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data: int) -> int:
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
return self.head.data
def middle_element(self) -> int:
"""
>>> link = LinkedList()
>>> link.middle_element()
No element found.
>>> link.push(5)
5
>>> link.push(6)
6
>>> link.push(8)
8
>>> link.push(8)
8
>>> link.push(10)
10
>>> link.push(12)
12
>>> link.push(17)
17
>>> link.push(7)
7
>>> link.push(3)
3
>>> link.push(20)
20
>>> link.push(-20)
-20
>>> link.middle_element()
12
>>>
"""
slow_pointer = self.head
fast_pointer = self.head
if self.head:
while fast_pointer and fast_pointer.next:
fast_pointer = fast_pointer.next.next
slow_pointer = slow_pointer.next
return slow_pointer.data
else:
print("No element found.")
if __name__ == "__main__":
link = LinkedList()
for i in range(int(input().strip())):
data = int(input().strip())
link.push(data)
print(link.middle_element())
