पायथन में पैलिंड्रोम लिंक्ड लिस्ट

मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें जांचना है कि लिस्ट के एलिमेंट्स पैलिंड्रोम बनाते हैं या नहीं। इसलिए यदि लिस्ट एलिमेंट [1,2,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([1,2,3,2,1])
ob1 = Solution()
print(ob1.isPalindrome(head))

इनपुट

[1,2,3,2,1]

आउटपुट

True