ভূমিকা
লিংকড লিস্টের মাঝপথের নোড (Middle node) বের করা: লিস্টের লেংথ জোড় হলে দুইটি মাঝপথের নোড থাকে, বিস্ম হলে একটি। দুই পাস পদ্ধতিতে লেংথ বের করে (length-1)//2 ধাপ এগিয়ে যাওয়া হয়।
উদাহরণ কোড
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def print_middle_val(my_list):
curr = my_list.head
my_len = 0
while curr:
curr = curr.next
my_len += 1
curr = my_list.head
for i in range((my_len - 1) // 2):
curr = curr.next
if curr:
if my_len % 2 == 0:
print('The two middle elements are {} and {}'.format(curr.data, curr.next.data))
else:
print('The middle-most element is {}.'.format(curr.data))
else:
print('The list is empty')
my_instance = LinkedList_structure()
my_list = input('Enter the elements of the linked list... ').split()
for elem in my_list:
my_instance.add_vals(int(elem))
print_middle_val(my_instance)
আউটপুট
Enter the elements of the linked list... 56 23 78 99 34 11 The two middle elements are 78 and 99
ব্যাখ্যা
লিস্ট: 56→23→78→99→34→11 (লেংথ ৬, জোড়)।
(my_len - 1) // 2= (5)//2 = 2। হেড থেকে ২ ধাপ এগিয়ে ৭৮ (০-বেসড ইনডেক্স ২)। পরবর্তী নোড ৯৯।জোড় লেংথের জন্য দুটি মাঝপথের নোড প্রিন্ট করা হয়।
O(1) স্পেস সমাধান (Slow & Fast Pointer)
def print_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if not slow:
print("Empty")
elif fast: # odd length, fast reached end (not None)
print("Middle:", slow.data)
else: # even length, fast became None
print("Two middles:", slow.data, slow.next.data)
fast ২x স্পিডে চলে। fast শেষে পৌঁছালে slow মাঝপথে থাকে। এক পাস, O(1) স্পেস।
