সমস্যা বিবরণ
একটি লিংকড লিস্ট দেওয়া আছে। যাচাই করতে হবে লিস্টের উপাদানগুলো প্যালিনড্রোম (উল্টা পড়লেও একই) কিনা।
উদাহরণ: [1,2,3,2,1] একটি প্যালিনড্রোম লিংকড লিস্ট।
সমাধানের পদ্ধতি
- দুটি পয়েন্টার (fast, slow) এবং একটি রিভার্সড লিস্ট (rev) ব্যবহার করুন।
- Fast পয়েন্টার ২ গতিতে, slow পয়েন্টার ১ গতিতে এগিয়ে যেতে থাকবে।
- Slow পয়েন্টার যেভাবে এগিয়ে যায়, তেভাবে লিস্টের প্রথমার্ধটিকে রিভার্স করুন।
- মাঝপথে পৌঁছালে দ্বিতীয়ার্ধের সাথে রিভার্স করা প্রথমার্ধ তুলনা করুন।
- সব মিললে true, না মিললে false ফেরত দিন।
পাইথন উদাহরণ
class ListNode:
def __init__(self, data, next=None):
self.data = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
class Solution(object):
def isPalindrome(self, head):
fast, slow = head, head
rev = None
flag = 1
if not head:
return True
while fast and fast.next:
if not fast.next.next:
flag = 0
break
fast = fast.next.next
temp = slow
slow = slow.next
temp.next = rev
rev = temp
fast = slow.next
slow.next = rev
if flag:
slow = slow.next
while fast and slow:
if fast.data != slow.data:
return False
fast = fast.next
slow = slow.next
return True
head = make_list([1,2,3,2,1])
ob1 = Solution()
print(ob1.isPalindrome(head))
ইনপুট
[1,2,3,2,1]
আউটপুট
True
