মান ল করুন একটি লিংকড লিস্ট। আমাদের যাচাই করতে হবে লিস্টের এলিমেন্টগুলো প্যালিনড্রোম বানাচ্ছে কিনা। যেমন লিস্ট [5,4,3,4,5] হলে এটি প্যালিনড্রোম, কিন্তু [5,4,3,2,1] প্যালিনড্রোম নয়।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- fast := head, slow := head, rev := None এবং flag := 1
- যদি head খালি হয়, তবে true ফেরত দিন
- যখন fast এবং fast.next থাকে:
- যদি fast.next.next থাকে, flag := 0 এবং লুপ ভাঙুন
- fast := fast.next.next
- temp := slow, slow := slow.next
- temp.next := rev, rev := temp
- fast := slow.next, slow.next := rev
- যদি flag সেট থাকে, slow := slow.next
- যখন fast এবং slow None না হয়:
- যদি fast.data != slow.data, false ফেরত দিন
- fast := fast.next, slow := slow.next
- true ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
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([5,4,3,4,5]) ob1 = Solution() print(ob1.isPalindrome(head))
ইনপুট
[5,4,3,4,5]
আউটপুট
True
