පාලින්ඩ්‍රෝම් සම්බන්ධිත ලැයිස්තුව ලීට්කෝඩ් විසඳුම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ප්රාග්ධන එක් සිස්කෝ ෆේස්බුක් ගූගල් පැහැර ගන්න ඉන්ටෙල් අයිඑක්ස්එල් මයික්රොසොෆ්ට් නූටනික්ස් ඔරකල් Paytm Snapchat Uber Yandex
ඇල්ගොරිතම කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions සම්බන්ධිත ලැයිස්තුව පොයින්ටර් දෙකක්

“පාලින්ඩ්‍රෝම් සම්බන්ධිත ලැයිස්තුව” ගැටලුවේදී, ලබා දී ඇති තනි පූර්ණ සංඛ්‍යාවක් දැයි අප විසින් පරීක්ෂා කළ යුතුය සම්බන්ධිත ලැයිස්තුව පාලින්ඩ්‍රෝම් හෝ නොවේ.

උදාහරණයක්  

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

පැහැදිලි කිරීම # 1: ආරම්භයේ සහ පිටුපස ඇති සියලුම මූලද්‍රව්‍යයන් එක සමාන අගයක් ගන්නා බැවින් ලැයිස්තුව පාලින්ඩ්‍රෝම් වේ.

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

පැහැදිලි කිරීම # 2: පිටුපසට හා පසුපසට යන මූලද්‍රව්‍යයන් එක හා සමාන නොවන බැවින් ලැයිස්තුව පාලින්ඩ්‍රෝම් නොවේ.

ප්‍රවේශය (රචනය 

පාලින්ඩ්‍රෝම් ගුණාංග පරීක්ෂා කිරීම සඳහා අරාවේ පිටුපස සිට නෝඩ් වල විස්තර අප සතුව තිබිය යුතු බව මෙය පහසුවෙන් හඳුනාගත හැකිය. මෙම අවස්ථාවේ දී, අපට a තනි සම්බන්ධිත ලැයිස්තුවේ තේරුම අපට ඕනෑම නෝඩයකට ළඟා වීමට ඉදිරියට යා හැකි බවයි. මේ අනුව, පිටුපස සිට නෝඩ් රඳවා තබා ගැනීම සඳහා යම් දත්ත ව්‍යුහයක් භාවිතා කිරීම වැදගත් වේ, උදා අඩුයි විය හැකි විකල්පයක් වන අතර එය නවතම නෝඩය ඉහළින් තබා ගනී. අපට පුනරාවර්තනය ද ඒ හා සමානව භාවිතා කළ හැකිය. පුනරාවර්තනය යනු නෝඩ් අගයන් ප්‍රතිලෝම අනුපිළිවෙලට ලබා ගැනීම සඳහා අලංකාරයකි. වඩා හොඳ අවබෝධයක් සඳහා පහත පොදු ව්‍යාජ කේතය සලකා බලන්න:

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

ඉහත කේතය පළමුව මුද්‍රණය කරයි වම් ගසෙහි ඇති නෝඩ්, අපි නැවත නැවත ශ්‍රිතය ලෙස හඳුන්වන්නේ නෝඩයේ වටිනාකම මුද්‍රණය කිරීමට පෙර ඕනෑම මූලයක වම් දරුවන් වෙත යාමයි. ඒ හා සමානව, අපට භාවිතා කළ හැකිය පුනරාවර්තනය පළමුව අන්තිම නෝඩ් වෙත යාමට සහ ශ්‍රිතය පසුපසට යන විට, අපට නෝඩ් අගයන් ප්‍රතිලෝම අනුපිළිවෙලින් ලැබෙනු ඇත. ඉදිරියට යාම සඳහා අපි විචල්‍යයක් භාවිතා කරන අතර එය පුනරාවර්තනයෙන් බලපෑමට ලක් නොවනු ඇත. මේ ආකාරයෙන්, අපට මූලද්‍රව්‍ය සංසන්දනය කිරීම සඳහා පුනරාවර්තනයෙන් ලබාගත් ඉදිරි ක්‍රියාකාරීත්වයේ අගය සහ ප්‍රතිලෝම නෝඩයේ අගය සංසන්දනය කළ හැකිය.

මෙයද බලන්න
IP ලිපින ලීට්කෝඩ් විසඳුමක් ඉවත් කිරීම

ඇල්ගොරිතම

  1. ශ්‍රිතයක් isPalindrome () සමඟ ලැයිස්තුවක් තිබේද යන්න ආපසු ලබා දීමට භාවිතා කරයි හිස palindrome හෝ නැත
  2. පංතියේ දත්ත සාමාජිකයෙකු ලෙස අපි නම් කරමු ඉදිරිපස ඉදිරි පුනරාවර්තන සඳහා නෝඩ් ගබඩා කිරීමට
  3. In isPalindrom ():
    • ආරම්භ කරන්න ඉදිරිපස = හිස
    • ආපසු palindromeCheck (හිස)
  4. In palindromeCheck (දැනට):
    • If දැනට is ශුන්ය:
      • ආපසු සැබෑ
    • If palindromeCheck (ධාරාව. ඊළඟ) is බොරු:
      • ආපසු බොරු
    • If වර්තමාන අගය is නැත සමානයි ඉදිරිපස. අගය
      • ආපසු බොරු
    • වර්ධක ඉදිරිපස:
      • front = front.next ඊළඟට
    • ආපසු සැබෑ අපි සියලු චෙක්පත් සිදු කළ නිසා
  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. භාවිතයෙන් සම්බන්ධිත ලැයිස්තුවේ මැද සොයා ගන්න middleOfList (හිසශ්රිතය:
    • දර්ශක දෙකක් ආරම්භ කරන්න මන්දගාමී වේ සහ ඉක්මනින් දෙකම ලැයිස්තුවේ හිසට යොමු කරයි
    • තුරු වේගයෙන්. ඊළඟට සහ fast.next.next දෙකම නැත ශූන්‍ය:
      1. වැඩි කිරීම මන්දගාමී වේ 1 වන විට, සෙමින් = සෙමින්. ඊළඟට
      2. වැඩි කිරීම ඉක්මනින් 2 වන විට, වේගයෙන් = වේගයෙන්. ඊළඟට. ඊළඟට
    • මන්දගාමී වේ දර්ශකය දැන් ලැයිස්තුවේ මැදට යොමු කරයි
    • ආපසු මන්දගාමී වේ
  3. දැන් අපි ලැයිස්තු ඇමතුමේ දෙවන භාගය ආපසු හරවන්නෙමු ප්‍රතිලෝම ලැයිස්තුව (හිස = මැද. ඊළඟට) ක්රියාව
    • ආරම්භ කරන්න පෙර = ශුන්ය
    • අතර හිස ශුන්‍ය නොවේ:
      • ඊළඟ නෝඩය තාවකාලික විචල්‍යයක ගබඩා කරන්න ඊලඟ
      • භාවිතයෙන් දර්ශක දිශාව ආපසු හරවන්න head.next = පෙර
      • prev = හිස
      • භාවිතයෙන් ලැයිස්තුවේ ඉදිරියට යන්න head = ඊළඟට
    • ආපසු පෙර
  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 = ලැයිස්තුවේ ප්‍රමාණය.

මෙයද බලන්න
K ට වඩා අඩු හෝ සමාන සියලුම මූලද්‍රව්‍ය එකට ගෙන ඒමට අවශ්‍ය අවම හුවමාරුව

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අපි භාවිතා කරන්නේ නියත අමතර ඉඩක් පමණි.