பாலிண்ட்ரோம் இணைக்கப்பட்ட பட்டியல் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் மூலதன ஒன்று சிஸ்கோ பேஸ்புக் கூகிள் கிராப் இன்டெல் IXL மைக்ரோசாப்ட் Nutanix ஆரக்கிள் Paytm 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. ஒரு செயல்பாடு isPalindrome () ஒரு பட்டியலுடன் உள்ளதா என்பதைத் திரும்பப் பயன்படுத்தப்படுகிறது தலை palindrome அல்லது இல்லை
  2. வகுப்பின் தரவு உறுப்பினரை நாங்கள் அறிவிக்கிறோம் முன் முன்னோக்கி மறு செய்கைகளுக்கு முனைகளை சேமிக்க
  3. In isPalindrom ():
    • துவக்க முன் = தலை
    • return palindromeCheck (தலை)
  4. In palindromeCheck (தற்போதைய):
    • If தற்போதைய is பூஜ்ய:
      • திரும்ப உண்மை
    • If palindromeCheck (current.next) is தவறான:
      • திரும்ப தவறான
    • If தற்போதைய மதிப்பு is இல்லை சமமாக front.value
      • திரும்ப தவறான
    • முன் அதிகரிக்கும்:
      • முன் = முன். அடுத்த
    • திரும்ப உண்மை நாங்கள் எல்லா காசோலைகளையும் செய்தோம்
  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 மற்றும் fast.next.next இரண்டும் இல்லை ஏதுமில்லை:
      1. உயர்வு மெதுவாக 1 வாக்கில், slow = slow.next
      2. உயர்வு வேகமாக 2 வாக்கில், fast = fast.next.next
    • மெதுவாக சுட்டிக்காட்டி இப்போது பட்டியலின் நடுவில் சுட்டிக்காட்டுகிறது
    • திரும்ப மெதுவாக
  3. இப்போது பட்டியல் அழைப்பின் இரண்டாம் பாதியை மாற்றியமைக்கிறோம் தலைகீழ் பட்டியல் (தலை = middle.next) செயல்பாடு
    • துவக்க முந்தைய = பூஜ்ய
    • போது தலை பூஜ்யமானது அல்ல:
      • அடுத்த முனையை ஒரு தற்காலிக மாறியில் சேமிக்கவும் அடுத்த
      • பயன்படுத்தி சுட்டிக்காட்டி திசையை மாற்றியமைக்கவும் head.next = கடந்த
      • 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) நிலையான நிலையான இடத்தை மட்டுமே நாங்கள் பயன்படுத்துகிறோம்.