मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें जांचना है कि क्या लिस्ट तत्व पैलिंड्रोम बना रहे हैं या नहीं। इसलिए यदि लिस्ट तत्व [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 का मान slow के मान के समान नहीं है, तो 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
