पायथन प्रोग्राम: जांचना कि सिंगली लिंक्ड लिस्ट पैलिंड्रोम है या नहीं

जब यह जांचने की आवश्यकता होती है कि सिंगली लिंक्ड लिस्ट पैलिंड्रोम है या नहीं, तो तत्व जोड़ने, पिछला नोड प्राप्त करने और जांचने के लिए मेथड्स परिभाषित की जाती हैं कि क्या पैलिंड्रोम बनता है।

उदाहरण

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList_struct:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_elements(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 get_previous_node(self, ref_node):
        curr = self.head
        while (curr and curr.next != ref_node):
            curr = curr.next
        return curr

def check_palindrome(my_list):
    beg = my_list.head
    end = my_list.last_node
    while (beg != end and end.next != beg):
        if beg.data != end.data:
            return False
        beg = beg.next
        end = my_list.get_previous_node(end)
    return True

my_instance = LinkedList_struct()
my_input = input('लिंक्ड लिस्ट में तत्व दर्ज करें: ').split()
for data in my_input:
    my_instance.add_elements(int(data))

if check_palindrome(my_instance):
    print('लिंक्ड लिस्ट प्रकृति में पैलिंड्रोमिक है')
else:
    print('लिंक्ड लिस्ट प्रकृति में पैलिंड्रोमिक नहीं है')

आउटपुट

लिंक्ड लिस्ट में तत्व दर्ज करें: 89 90 78 90 89
लिंक्ड लिस्ट प्रकृति में पैलिंड्रोमिक है

व्याख्या

• 'Node' क्लास बनाई गई है।

• आवश्यक विशेषताओं के साथ एक अन्य 'LinkedList_struct' क्लास बनाई गई है।

• इसमें एक 'init' फ़ंक्शन है जो पहले तत्व, यानी 'head' को 'None' और अंतिम नोड को 'None' पर इनिशियलाइज़ करता है।

• 'add_elements' नामक एक अन्य मेथड परिभाषित की गई है, जिसका उपयोग लिंक्ड लिस्ट में पिछले नोड को प्राप्त करने के लिए किया जाता है।

• 'get_previous_node' नामक एक अन्य मेथड कंसोल पर लिंक्ड लिस्ट डेटा प्रदर्शित करने के लिए परिभाषित की गई है।

• 'check_palindrome' नामक एक मेथड परिभाषित की गई है, जो पहले और अंतिम तत्व की तुलना करती है, यदि वे समान नहीं हैं, तो यह निर्धारित करती है कि सूची पैलिंड्रोमिक प्रकृति की नहीं थी।

• 'LinkedList_struct' क्लास का एक ऑब्जेक्ट बनाया जाता है।

• लिंक्ड लिस्ट में तत्वों के लिए उपयोगकर्ता इनपुट लिया जाता है।

• तत्वों को लिंक्ड लिस्ट में जोड़ा जाता है।

• इस लिंक्ड लिस्ट पर 'check_palindrome' मेथड कॉल की जाती है।

• प्रासंगिक आउटपुट कंसोल पर प्रदर्शित होता है।

एल्गोरिदम विश्लेषण

• समय जटिलता: O(n²) - प्रत्येक चरण के लिए get_previous_node O(n) लेता है

• स्थान जटिलता: O(1) - अतिरिक्त स्थान नहीं

अधिक कुशल दृष्टिकोण (O(n) समय, O(1) स्थान)

1. धीमे और तेज़ पॉइंटर का उपयोग करके मध्य खोजें

2. दूसरे आधे को रिवर्स करें

3. दोनों आधे की तुलना करें

4. दूसरे आधे को फिर से रिवर्स करके सूची पुनर्स्थापित करें (वैकल्पिक)

def check_palindrome_optimized(head):
    if not head or not head.next:
        return True
    
    # मध्य खोजें
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # दूसरा आधा रिवर्स करें
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt
    
    # तुलना करें
    first, second = head, prev
    result = True
    while second:
        if first.data != second.data:
            result = False
            break
        first = first.next
        second = second.next
    
    # वैकल्पिक: सूची पुनर्स्थापित करें
    # ...
    return result

टेस्ट केस

• [1, 2, 3, 2, 1] → True

• [1, 2, 2, 1] → True

• [1, 2, 3] → False

• [1] → True

• [] → True