class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        regularListHead = ListNode(-1)
        regularListHead.next = head
        reverseListHead = head

        reverseListPrev = None
        reverseListCurrent = reverseListHead

        while reverseListCurrent != None:
            reverseListNext = reverseListCurrent.next
            reverseListCurrent.next = reverseListPrev
            reverseListPrev = reverseListCurrent
            reverseListCurrent = reverseListNext
        reverseListHead = reverseListPrev
        a = regularListHead

मेरे कोड में, मैं मूल सूची को उलटी सूची में बदलने की कोशिश कर रहा हूं और पैलिंड्रोम की जांच के लिए दोनों की तुलना करता हूं, लेकिन जब मैं रिवर्सलिस्ट को उलटने के लिए ऑपरेशन करता हूं तो मूल सूची भी अपडेट हो जाती है। मैं अजगर के लिए नया हूं क्या कोई मुझे बता सकता है कि ऐसा क्यों हो रहा है और जो मैं चाहता हूं उसे हासिल करने के लिए क्या किया जा सकता है?

0
Ajinkya Gadgil 23 अप्रैल 2021, 16:04
1
केवल एक सूची है। आप इसे जगह-जगह संशोधित कर रहे हैं। आप कभी भी कोई नई सूची नहीं बनाते हैं, या कुछ भी कॉपी नहीं करते हैं। निम्नलिखित उपयोगी होना चाहिए: nedbatchelder.com/text/names.html
 – 
juanpa.arrivillaga
23 अप्रैल 2021, 16:07

1 उत्तर

सबसे बढ़िया उत्तर

आप केवल एक नया नोड बनाते हैं। अन्य सभी नोड आपकी मूल सूची के नोड हैं, और आप उनके next गुणों को अपडेट करते हैं ताकि सूची उलट जाए।

इसलिए यदि आप दोनों मूल और उलटी सूची रखना चाहते हैं, तो आपके पास दो सूचियां होनी चाहिए, जिनमें से प्रत्येक का अपना नोड होगा:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return
        # Create reversed list
        revHead = ListNode(head.val)
        current = head.next
        while current is not None:
            revHead = ListNode(current.val, revHead)
            current = current.next
    
        # Compare original with the reversed one
        while head is not None:
            if head.val != revHead.val:
                return False
            head = head.next
            revHead = revHead.next
        return True

हालांकि यह इष्टतम नहीं है: तुलना लूप को केवल 𝑛/2 तुलना करने की आवश्यकता है, न कि ।

आप अपने आप से यह भी पूछ सकते हैं कि आप उल्टे संस्करण के लिए एक लिंक्ड सूची क्यों बनाएंगे: क्योंकि यह केवल पैलिंड्रोम जांच के लिए आवश्यक है, आप एक मानक सूची भी बना सकते हैं, और फिर पैलिंड्रोम की जांच कर सकते हैं बस वह सूची, जो केक का एक टुकड़ा है।

लेकिन इससे भी महत्वपूर्ण बात यह है कि एक नई सूची (चाहे लिंक की गई सूची या सामान्य "सरणी" सूची) बनाने के लिए O(n) अतिरिक्त स्थान की आवश्यकता होती है। यदि आप नए नोड्स बनाए बिना ऐसा करने के लिए एक एल्गोरिथ्म में रुचि रखते हैं, तो इसे लागू करने का प्रयास करें:

  1. सूची में नोड्स की संख्या की गणना करें
  2. सूची के दूसरे भाग के पहले नोड की पहचान करने के लिए इसका इस्तेमाल करें। यदि नोड्स की संख्या विषम है, तो इसे केंद्रीय नोड के बाद नोड होने दें।
  3. उस दूसरी छमाही में एक इन-प्लेस लिस्ट रिवर्सल एल्गोरिदम लागू करें। अब आपके पास दो छोटी सूचियाँ हैं।
  4. उन दो सूचियों में मानों की तुलना करके देखें कि क्या वे समान हैं (यदि कोई हो तो केंद्र नोड पर ध्यान न दें)। परिणाम याद रखें (झूठा या सच)
  5. वैकल्पिक रूप से चरण 3 को दोहराएं ताकि रिवर्सल वापस लुढ़क जाए, और सूची अपनी मूल स्थिति में वापस आ जाए। (यह आपके फ़ंक्शन के कॉलर की ओर "अच्छा" है)
  6. चरण 4 में मिले परिणाम को वापस करें।
0
trincot 23 अप्रैल 2021, 23:03
विस्तृत जानकारी के लिए धन्यवाद। मैंने आपके द्वारा बताए गए समान इष्टतम दृष्टिकोण को पहले ही लागू कर दिया है। प्रारंभ में मैं सिर्फ एक क्रूर बल दृष्टिकोण के बारे में सोच रहा था क्योंकि मेरा पहला दृष्टिकोण इस समस्या का सामना कर रहा था। अपने स्पष्टीकरण के लिए धन्यवाद।
 – 
Ajinkya Gadgil
23 अप्रैल 2021, 23:15
नमस्ते, कोई भी अच्छा पायथन ट्यूटोरियल जो अवधारणाओं को विस्तार से संदर्भित करेगा और सामान्य रूप से सभी मूल बातें?
 – 
Ajinkya Gadgil
23 अप्रैल 2021, 23:42
सुनिश्चित नहीं है कि सबसे अच्छा कहाँ जाना है। लेकिन पायथन ट्यूटर कोड निष्पादन के दौरान स्मृति को देखने में मदद करता है।
 – 
trincot
23 अप्रैल 2021, 23:58