പലിൻഡ്രോം ലിങ്ക്ഡ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരം  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ക്യാപിറ്റൽ വൺ സിസ്കോ ഫേസ്ബുക്ക് ഗൂഗിൾ എടുക്കുക ഇന്റൽ IXL മൈക്രോസോഫ്റ്റ് നൂതാനിക്സ് ഒറാക്കിൾ Paytm Snapchat യൂബർ യാൻഡക്സ്
അൽഗോരിതം കോഡിംഗ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions ലിങ്ക്ഡ്-ലിസ്റ്റ് രണ്ട് പോയിന്ററുകൾ

“പലിൻഡ്രോം ലിങ്കുചെയ്‌ത ലിസ്റ്റ്” എന്ന പ്രശ്‌നത്തിൽ, തന്നിരിക്കുന്ന ഒറ്റ സംഖ്യയാണോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഒരു പലിൻഡ്രോം അല്ലെങ്കിൽ അല്ല.

ഉദാഹരണം  

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 () ഉള്ള ഒരു ലിസ്റ്റ് മടക്കിനൽകാൻ ഉപയോഗിക്കുന്നു തല പലിൻഡ്രോം അല്ലെങ്കിൽ അല്ല
  2. ക്ലാസിലെ ഒരു ഡാറ്റാ അംഗത്തെ ഞങ്ങൾ പ്രഖ്യാപിക്കുന്നു ഫ്രണ്ട് ഫോർവേഡ് ആവർത്തനത്തിനായി നോഡുകൾ സംഭരിക്കുന്നതിന്
  3. In isPalindrom ():
    • ആരംഭിക്കുക ഫ്രണ്ട് = തല
    • മടങ്ങുക palindromeCheck (തല)
  4. In palindromeCheck (നിലവിലുള്ളത്):
    • If നിലവിലുള്ളത് is ശൂന്യം:
      • മടക്കം യഥാർഥ
    • If palindromeCheck (നിലവിലെ. അടുത്തത്) 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

പലിൻഡ്രോം ലിങ്ക്ഡ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ആവർത്തനം ഉപയോഗിച്ച് ഒരിക്കൽ ഞങ്ങൾ പട്ടികയിലൂടെ സഞ്ചരിക്കുമ്പോൾ. ഇവിടെ, പട്ടികയിലെ N = നോഡുകളുടെ എണ്ണം.

ഇതും കാണുക
ബൈനറി ട്രീ സീരിയലൈസ് ചെയ്യുകയും ഡിസീരിയലൈസ് ചെയ്യുകയും ചെയ്യുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) സൃഷ്ടിക്കുന്ന ഓരോ നോഡും പരിശോധിക്കാൻ ഞങ്ങൾ ഒരു ആവർത്തന ഫംഗ്ഷൻ വിളിക്കുന്നു N മെമ്മറികളിൽ ഫ്രെയിമുകൾ അടുക്കുക.

സമീപനം (മറ്റ് പകുതി വിപരീതമാക്കുക)  

ആവർത്തനത്തിനായി ഉപയോഗിച്ച ഇടം ഒഴിവാക്കാനുള്ള ഏക മാർഗം തന്നിരിക്കുന്ന പട്ടിക സ്ഥലത്ത് പരിഷ്കരിക്കുക എന്നതാണ്. ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ രണ്ടാം പകുതി ഞങ്ങൾ വിപരീതമാക്കുകയും അനുബന്ധ മൂല്യങ്ങൾ തുല്യമാണോ എന്ന് പരിശോധിക്കുന്നതിന് രണ്ട് ഭാഗങ്ങൾക്കും രണ്ട് ഫോർവേഡ് ഇറ്ററേറ്ററുകൾ ഉപയോഗിക്കുന്നു. ഈ പ്രക്രിയയ്ക്കായി, ഞങ്ങൾ ഇവ ചെയ്യേണ്ടതുണ്ട്:

  • പട്ടികയുടെ മധ്യഭാഗം കണ്ടെത്തുന്നതിലൂടെ രണ്ടാം പകുതി നമുക്ക് തിരിച്ചെടുക്കാനാകും.
  • ലിസ്റ്റിന്റെ രണ്ടാം പകുതി മാറ്റാൻ ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക
  • ഒന്നും രണ്ടും പകുതി തുല്യമാണോയെന്ന് പരിശോധിക്കുക

മേൽപ്പറഞ്ഞവയെല്ലാം രേഖീയ സമയത്ത് ചെയ്യാം. ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഞങ്ങൾ റിവേഴ്‌സ് ചെയ്ത ശേഷം, രണ്ടാം പകുതി പൂർത്തിയാകുന്നതുവരെ ഞങ്ങൾ പരിശോധിക്കാൻ ആരംഭിക്കുന്നു.

പലിൻഡ്രോം ലിങ്ക്ഡ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരംമൊട്ടുസൂചി

അൽഗോരിതം

  1. If തല is ശൂന്യം:
    • ശരിയായി മടങ്ങുക
  2. ഉപയോഗിച്ച് ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ മധ്യഭാഗം കണ്ടെത്തുക മിഡിൽ‌ഓഫ്‌ലിസ്റ്റ് (തലപ്രവർത്തനം:
    • രണ്ട് പോയിന്ററുകൾ സമാരംഭിക്കുക പതുക്കെ ഒപ്പം ഉപവാസം രണ്ടും പട്ടികയുടെ തലയിലേക്ക് വിരൽ ചൂണ്ടുന്നു
    • വരുവോളം വേഗം. അടുത്തത് ഒപ്പം fast.next.next രണ്ടും അല്ല ശൂന്യം:
      1. ഇൻക്രിമെന്റും പതുക്കെ 1 ഓടെ, പതുക്കെ = പതുക്കെ. അടുത്തത്
      2. ഇൻക്രിമെന്റും ഉപവാസം 2 ഓടെ, ഫാസ്റ്റ് = fast.next.next
    • പതുക്കെ പോയിന്റർ ഇപ്പോൾ പട്ടികയുടെ മധ്യത്തിലേക്ക് വിരൽ ചൂണ്ടുന്നു
    • മടക്കം പതുക്കെ
  3. ഇപ്പോൾ ഞങ്ങൾ ലിസ്റ്റ് കോളിംഗിന്റെ രണ്ടാം പകുതി തിരിച്ചിടുന്നു വിപരീത ലിസ്റ്റ് (തല = മധ്യ. അടുത്തത്) ഫംഗ്ഷൻ
    • സമാരംഭിക്കുക മുമ്പത്തേത് = ശൂന്യം
    • സമയത്ത് തല ശൂന്യമല്ല:
      • അടുത്ത നോഡ് ഒരു താൽക്കാലിക വേരിയബിളിൽ സംഭരിക്കുക തൊട്ടടുത്ത
      • ഉപയോഗിച്ച് പോയിന്റർ ദിശ വിപരീതമാക്കുക 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

പലിൻഡ്രോം ലിങ്ക്ഡ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ലിസ്റ്റിന്റെ മധ്യഭാഗം കണ്ടെത്താനും അത് വിപരീതമാക്കാനും രണ്ട് ഭാഗങ്ങളും താരതമ്യം ചെയ്യാനും ഞങ്ങൾ ലീനിയർ ലൂപ്പുകൾ ഉപയോഗിക്കുമ്പോൾ. ഇവിടെ, N = പട്ടികയുടെ വലുപ്പം.

ഇതും കാണുക
എല്ലാ ഘടകങ്ങളും k- നേക്കാൾ കുറവോ തുല്യമോ ഒരുമിച്ച് കൊണ്ടുവരാൻ ആവശ്യമായ കുറഞ്ഞ സ്വാപ്പുകൾ

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ അധിക ഇടം മാത്രം ഉപയോഗിക്കുന്നതിനാൽ.