पलिंड्रोम लिस्टेड लेटकोड सॉल्यूशन


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग एक राजधानी सिस्को Facebook गूगल कब्र इंटेल IXL माइक्रोसॉफ्ट Nutanix ओरेकल Paytm Snapchat Uber Yandex
लिंक्ड सूची दो संकेत

समस्या "पैलिंड्रोम लिंक्ड सूची" में, हमें यह जांचना होगा कि क्या एक दिया गया पूर्णांक है लिंक्ड सूची एक palindrome है या नहीं।

उदाहरण

List = {1 -> 2 -> 3 -> 2 -> 1}
true

स्पष्टीकरण # 1: सूची पैलिंद्रोम है क्योंकि प्रारंभ और बैक से सभी तत्व समान हैं।

List = {1 -> 2 -> 3 -> 4 -> 5}
false

स्पष्टीकरण # 2: सूची पैलिंड्रोम नहीं है क्योंकि आगे और पीछे के तत्व समान नहीं हैं।

दृष्टिकोण (Recursion)

यह नोटिस करना आसान है कि हमें palindrome संपत्तियों की जांच के लिए सरणी के पीछे से नोड्स का विवरण होना चाहिए। इस मामले में, हमने ए अकेले लिंक की गई सूची का अर्थ है कि हम केवल किसी भी नोड तक पहुंचने के लिए आगे बढ़ना कर सकते हैं। इस प्रकार, पीछे से नोड्स को पकड़ने के लिए कुछ डेटा संरचना का उपयोग करना महत्वपूर्ण हो जाता है, जैसे धुआँरा एक संभावित विकल्प है क्योंकि यह सबसे हालिया नोड को सबसे ऊपर रखता है। हम भी इसी तरह पुनरावृत्ति का उपयोग कर सकते हैं। रिवर्स ऑर्डर में नोड मान प्राप्त करने के लिए रिकर्सियन एक सुरुचिपूर्ण है। बेहतर समझ के लिए नीचे दिए गए सामान्य छद्मकोश पर विचार करें:

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

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

कलन विधि

  1. एक समारोह isPalindrome () का उपयोग किसी सूची के साथ करने के लिए किया जाता है सिर palindrome है या नहीं
  2. हम नामित कक्षा के एक डेटा सदस्य की घोषणा करते हैं सामने आगे पुनरावृत्तियों के लिए नोड्स को संग्रहीत करने के लिए
  3. In isPalindrom ():
    • हस्ताक्षर करना सामने = सिर
    • वापसी पैलिंद्रोमचेक (सिर)
  4. In palindromeCheck (वर्तमान):
    • If वर्तमान is रिक्त:
      • वापसी <strong>उद्देश्य</strong>
    • If palindromeCheck (वर्तमान.अगला) is असत्य:
      • वापसी असत्य
    • If वर्तमान मूल्य is नहीं के बराबर सामने
      • वापसी असत्य
    • वेतन वृद्धि का मोर्चा:
      • सामने = सामने
    • वापसी <strong>उद्देश्य</strong> जैसा कि हमने सभी चेक का प्रदर्शन किया
  5. परिणाम प्रिंट करें

पलिंड्रोम लिंक्ड लिस्टकोड समाधान का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

जावा प्रोग्राम

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

पैलिंड्रोम लिंक्ड लिस्टकोड समाधान का जटिलता विश्लेषण

समय जटिलता

पर) जैसा कि हम पुनरावृत्ति का उपयोग करके एक बार सूची को पार करते हैं। यहाँ, N = सूची में नोड्स की संख्या।

अंतरिक्ष जटिलता

पर) जैसा कि हम प्रत्येक नोड बनाने के लिए जाँच करने के लिए एक पुनरावर्ती कार्य कहते हैं N मेमोरी में स्टैक फ्रेम।

दृष्टिकोण (अन्य आधा उल्टा)

पुनरावृत्ति में उपयोग किए जाने वाले स्थान से छुटकारा पाने का एकमात्र तरीका दी गई सूची को इन-प्लेस में संशोधित करना है। हम लिंक की गई सूची के उत्तरार्ध को उल्टा करते हैं और फिर संबंधित हिस्सों के बराबर होने की जांच करने के लिए दोनों हिस्सों के लिए दो आगे चलने वाले का उपयोग करते हैं। इस प्रक्रिया के लिए, हमें निम्न करने की आवश्यकता है:

  • सूची के मध्य को खोजें ताकि हम दूसरी छमाही को उलट सकें।
  • सूची के दूसरे छमाही को उलटने के लिए एक फ़ंक्शन बनाएं
  • जाँच करें कि क्या पहली और दूसरी छमाही बराबर हैं

उपरोक्त सभी को रैखिक समय में किया जा सकता है। लिंक की गई सूची को उलटने के बाद, हम दूसरी छमाही पूरी होने तक जाँच करना शुरू करते हैं।

पलिंड्रोम लिस्टेड लेटकोड सॉल्यूशन

कलन विधि

  1. If सिर is रिक्त:
    • सच लौटाओ
  2. लिंक की गई सूची का उपयोग कर के बीच का पता लगाएं मिडऑफलिस्ट (सिरसमारोह:
    • दो पॉइंटर्स इनिशियलाइज़ करें धीमा और तेज दोनों सूची के प्रमुख की ओर इशारा करते हैं
    • जब तक फास्ट.अगला और तेज.अगला.अगला दोनों नहीं शून्य:
      1. वेतन वृद्धि धीमा 1 तक, धीमा = धीमा। अगला
      2. वेतन वृद्धि तेज 2 तक, तेज = तेज। अगला। अगला
    • धीमा सूचक अब सूची के मध्य की ओर इंगित करता है
    • वापसी धीमा
  3. अब हम सूची कॉलिंग की दूसरी छमाही को उल्टा करते हैं उल्टा (सिर) mid.next) समारोह
    • आरंभ पिछला = रिक्त
    • जब सिर निरर्थक नहीं है:
      • एक अस्थायी चर में अगले नोड को स्टोर करें, जैसा कि अगला
      • का उपयोग करके सूचक दिशा को उल्टा करें सिर.अगला = पिछला
      • prev = सिर
      • का उपयोग कर सूची में आगे बढ़ें सिर = अगला
    • वापसी पिछला
  4. अब, दो बिंदुओं को स्पष्ट करें पीटीआर1 और पीटीआर2 दोनों हिस्सों के माध्यम से पुनरावृति करने के लिए:
    1. पीटीआर 1 = सिर
    2. ptr2 = प्रारंभ दूसरी छमाही के
    3. जब पीटीआर2 निरर्थक नहीं है:
      1. if पीटीआर1.मूल्य के बराबर नहीं है पीटीआर2.मूल्य
        1. वापसी असत्य
    4. वापसी <strong>उद्देश्य</strong> जैसा कि हमने पहली और दूसरी छमाही में प्रत्येक नोड की जाँच की
  5. परिणाम प्रिंट करें

पलिंड्रोम लिंक्ड लिस्टकोड समाधान का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

जावा प्रोग्राम

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

पैलिंड्रोम लिंक्ड लिस्टकोड समाधान का जटिलता विश्लेषण

समय जटिलता

पर) जैसा कि हम सूची के मध्य को खोजने के लिए रैखिक छोरों का उपयोग करते हैं, इसे उल्टा करते हैं, और दोनों हिस्सों की तुलना करते हैं। यहाँ, N = सूची का आकार।

अंतरिक्ष जटिलता

ओ (1) जैसा कि हम केवल निरंतर अतिरिक्त स्थान का उपयोग करते हैं।