पालिंड्रोम लिंक्ड यादी लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग कॅपिटल वन सिस्को फेसबुक Google हस्तगत करा इंटेल आयएक्सएल मायक्रोसॉफ्ट न्युटॅनिक्स ओरॅकल पेटीएम Snapchat उबेर यांडेक्स
दुवा साधलेली यादी दोन पॉईंटर्स

“पॅलिंड्रोम लिंक्ड लिस्ट” या समस्येमध्ये, दिलेला एकल पूर्णांक आहे की नाही ते तपासावे लागेल जोडलेली यादी पॅलिंड्रोम आहे की नाही.

उदाहरण

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

स्पष्टीकरण # 1: सूची पॅलिंड्रोम आहे कारण सुरवातीपासून आणि मागील सर्व घटक मूल्यांमध्ये समान आहेत.

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

स्पष्टीकरण # 2: यादी पॅलिंड्रोम नाही कारण मागे आणि पुढे घटक सारखे नसतात.

दृष्टीकोन (पुनरावृत्ती)

हे लक्षात घेणे सोपे आहे की पालिंड्रोम गुणधर्म तपासण्यासाठी अ‍ॅरेच्या मागील बाजूस नोड्सचा तपशील असणे आवश्यक आहे. या प्रकरणात, आमच्याकडे ए एकटा लिंक्ड यादी म्हणजे कोणत्याही नोडपर्यंत पोहोचण्यासाठी आम्ही फक्त पुढे जाऊ शकतो. अशा प्रकारे, मागील नोड्स ठेवण्यासाठी काही डेटा स्ट्रक्चर वापरणे महत्वाचे होते, उदा स्टॅक हा एक संभाव्य पर्याय आहे कारण तो सर्वात अलीकडील नोडला सर्वात वर ठेवतो. आपण त्याच प्रमाणे रिकर्सन देखील वापरू शकतो. उलट क्रमाने नोड मूल्ये मिळविण्यासाठी रिकर्सन एक मोहक आहे. चांगल्या प्रकारे समजण्यासाठी खालील सामान्य स्यूडोकोडचा विचार करा:

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

वरील कोड प्रथम प्रिंट करतो बाकी झाडाच्या नोड्स कारण आम्ही नोडचे मूल्य प्रिंट करण्यापूर्वी कोणत्याही मुळांच्या डाव्या मुलांकडे जाण्यासाठी फंक्शनला पुन्हा कॉल करतो. तसेच आपण वापरू शकतो पुनरावृत्ती प्रथम शेवटच्या नोडवर जाण्यासाठी आणि जेव्हा फंक्शन बॅकट्रॅक होईल तेव्हा आपल्याला नोडची व्हॅल्यू रिव्हर्स क्रमाने मिळतील. पुढे चालण्यासाठी आम्ही एक व्हेरिएबल वापरू जे पुनरावृत्तीमुळे प्रभावित होणार नाही. अशा प्रकारे, घटकांची तुलना करण्यासाठी आम्ही आवर्ती पुनरावृत्ती करणार्‍याच्या मूल्याची आणि पुनरावृत्तीद्वारे प्राप्त नोडच्या मूल्याची तुलना करू शकतो.

अल्गोरिदम

  1. एक फंक्शन आयपॅलिंड्रोम () सह सूची आहे की नाही हे परत करण्यासाठी वापरले जाते डोके पॅलिंड्रोम आहे की नाही
  2. आम्ही नावाच्या वर्गाचा डेटा सदस्य घोषित करतो समोर पुढील पुनरावृत्तीसाठी नोड्स संचयित करण्यासाठी
  3. In isPalindrom ():
    • आरंभ करा समोर = डोके
    • रिटर्न पॅलिंड्रोमचेक (डोके)
  4. In पॅलिंड्रोमचेक (वर्तमान):
    • If वर्तमान is निरर्थक:
      • परत खरे
    • If पॅलिंड्रोमचेक (चालू.पुस्तक) is खोटे:
      • परत खोटे
    • If चालू.मूल्य is नाही च्या बरोबरीने समोर. मूल्य
      • परत खोटे
    • वाढीचा पुढील भाग:
      • समोर = समोर. पुढील
    • परत खरे जसे आम्ही सर्व तपासणी केली
  5. निकाल प्रिंट करा

पालिंड्रोम लिंक्ड यादी लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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. वापरून दुवा साधलेल्या सूचीच्या मध्यभागी शोधा मिडलऑफलिस्ट (डोकेकार्य:
    • दोन पॉईंटर्स प्रारंभ करा मंद आणि जलद दोघेही यादीच्या दिशेला जाऊ लागले
    • पर्यंत फास्ट.एन्क्स्ट आणि fast.next.next दोन्ही आहेत नाही निरर्थक:
      1. वाढ मंद 1 पर्यंत, धीमे = हळू.पुस्तक
      2. वाढ जलद 2 पर्यंत, वेगवान = fast.next.next
    • मंद पॉईंटर आता सूचीच्या मध्यभागी निर्देश करतो
    • परत मंद
  3. आता आम्ही यादी कॉलिंगच्या दुसर्‍या अर्ध्यावर उलट करतो रिव्हर्सलिस्ट (डोके = मध्यम) कार्य
    • आरंभ करा मागील = निरर्थक
    • तर डोके शून्य नाही:
      • पुढील नोडला तात्पुरत्या व्हेरिएबलमध्ये साठवा पुढील
      • वापरून पॉईंटर दिशेने उलट करा head.next = prev
      • prev = डोके
      • वापरून सूचीत पुढे जा डोके = पुढील
    • परत मागील
  4. आता दोन पॉईंटर्स अंतर्भूत करा ptr1 आणि ptr2 दोन्ही भागांमध्ये पुनरावृत्ती करणे:
    1. ptr1 = डोके
    2. ptr2 = प्रारंभ दुसर्‍या अर्ध्याचा
    3. तर ptr2 शून्य नाही:
      1. if ptr1.मूल्य च्या बरोबर नाही ptr2.मूल्य
        1. परत खोटे
    4. परत खरे जसे आम्ही पहिल्या आणि दुसर्‍या अर्ध्या भागातील प्रत्येक नोड तपासला
  5. निकाल प्रिंट करा

पालिंड्रोम लिंक्ड यादी लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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) कारण आम्ही फक्त सतत अतिरिक्त जागा वापरतो.