Palindrome Linked စာရင်း Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Capital One Cisco သည် Facebook က Google ဆုပ်ကိုင် Intel က IXL Microsoft က Nutanix Oracle က Paytm Snapchat Uber Yandex
ချိတ်ဆက်စာရင်း နှစ်ခုထောက်ပြ

ပြindနာ“ Palindrome Linked List” တွင်ကျွန်ုပ်တို့သည်တစ်ခုတည်းသောကိန်းပြည့်ဟုတ်မဟုတ်ကိုစစ်ဆေးရပါမည် ဆက်စပ်စာရင်း palindrome လားမပါဘူး။

နမူနာ

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

ရှင်းလင်းချက် # 1ဖြေ - စာရင်းက palindrome ဖြစ်တယ်။ ဘာလို့လဲဆိုတော့ start နဲ့ back က element အားလုံးတန်ဖိုးအတူတူပဲ။

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

ရှင်းလင်းချက် # 2ဖြေ - စာရင်းက palindrome မဟုတ်ပါဘူး။

ချဉ်းကပ်မှု (နေ့တိုင်းပြန်လည်စတင်မည်)

palindrome ဂုဏ်သတ္တိများကိုစစ်ဆေးရန်အတွက် array ၏နောက်ဖက်ရှိ node များ၏အသေးစိတ်အချက်အလက်များကိုကျွန်ုပ်တို့လိုအပ်သည်ကိုသတိပြုမိရန်လွယ်ကူသည်။ ဤကိစ္စတွင်ကျွန်ုပ်တို့သည်တစ် ဦး ရှိသည် တစ်ယောက်တည်း link list သည်မည်သည့် node ကိုမဆိုရောက်ရှိရန်ရှေ့ဆက်သွားနိုင်သည်ဟုဆိုလိုသည်။ ထို့ကြောင့်၊ ဥပမာကျောရိုးမှ node များကိုထိန်းသိမ်းရန်ဒေတာဖွဲ့စည်းပုံကိုအသုံးပြုရန်အရေးကြီးသည် စုပုံထား ထိပ်ဆုံးရှိနောက်ဆုံးပေါ် node ကိုသိမ်းထားသကဲ့သို့ဖြစ်နိုင်သော option တစ်ခုဖြစ်သည်။ ငါတို့သည်လည်းအလားတူ recursion ကိုသုံးနိုင်သည်။ Recursion သည် node တန်ဖိုးများကိုပြောင်းပြန်အစဉ်လိုက်အဆင်ပြေစေရန်ပြုလုပ်ပေးသည်။ ပိုမိုနားလည်ရန်အောက်ဖော်ပြပါအထွေထွေ pseudocode ကိုစဉ်းစားပါ -

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

အပေါ်ကကုဒ်ကိုအရင်ရိုက်တယ် လက်ဝဲဘက် သစ်ပင်အတွင်းရှိ node များသည် function ကို nurs ၏တန်ဖိုးကိုမပုံနှိပ်မီမည်သည့်အမြစ်မှကျန်ရှိသောကလေးများထံသို့သွားရန် function ကိုခေါ်သောကြောင့်ဖြစ်သည်။ အလားတူပဲကျနော်တို့ကိုသုံးနိုင်သည် ပြန်လည် ပထမဆုံး node ကိုအရင်သွားရန်နှင့် function သည်နောက်သို့ပြန်သွားပါက node တန်ဖိုးများကိုပြောင်းပြန်နိုင်ရန်ဖြစ်သည်။ ကျနော်တို့က recursion အားဖြင့်ထိခိုက်လိမ့်မည်သည့် forward iterate ဖို့ variable ကိုသုံးပါလိမ့်မယ်။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည် iterator ၏ forward နှင့် element များကိုနှိုင်းယှဉ်ရန် recursion မှရရှိသော reverse node ၏တန်ဖိုးကိုနှိုင်းယှဉ်နိုင်သည်။

algorithm

  1. function တစ်ခု isPalindrome () နှင့်အတူစာရင်းတစ်ခုရှိမရှိပြန်လာရန်အသုံးပြုသည် ဦးခေါင်း palindrome သို့မဟုတ်မဖြစ်ပါတယ်
  2. ကျနော်တို့အမည်ရှိအတန်း၏ဒေတာအဖွဲ့ဝင်ကြေညာ ရှေ့ ရှေ့သို့ကြားမှာများအတွက် node များသိုလှောင်ရန်
  3. In isPalindrom ():
    • စတငျ ရှေ့ = ခေါင်း
    • palindromeCheck ကိုပြန်သွားပါ (ဦး ခေါင်း)
  4. In palindromeCheck (ယခု):
    • If ယခု is တရားမဝင်သော:
      • ပြန်လာ စစ်မှန်တဲ့
    • If palindromeCheck (လက်ရှိ) is မမှန်သော:
      • ပြန်လာ မမှန်သော
    • If လက်ရှိ is မဟုတ် ညီမျှသည် မင်္ဂလာပါ
      • ပြန်လာ မမှန်သော
    • ရှေ့တိုးသည်
      • ရှေ့ = front.next
    • ပြန်လာ စစ်မှန်တဲ့ ငါတို့ရှိသမျှသည်စစ်ဆေးမှုများဖျော်ဖြေအဖြစ်
  5. ရလဒ်ပုံနှိပ်ပါ

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

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;
}

Java အစီအစဉ်

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

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ကျွန်တော်တစ်ချိန်က recursion သုံးပြီးစာရင်းဖြတ်သန်းအဖြစ်။ ဤတွင် N = စာရင်းထဲတွင် node များအရေအတွက်။

အာကာသရှုပ်ထွေးမှု

အို (N) node ဖန်တီးတိုင်းကိုစစ်ဆေးရန် recursive function ကိုခေါ်သည် N မှတ်ဉာဏ်ထဲမှာ frames များကို stack ။

ချဉ်းကပ်မှု (အခြားတစ်ဝက်ကိုပြောင်းပြန်)

recursion တွင်အသုံးပြုသောအာကာသကိုဖယ်ရှားရန်တစ်ခုတည်းသောနည်းလမ်းမှာပေးထားသောစာရင်းအားနေရာတွင်ပြုပြင်ခြင်းဖြစ်သည်။ ကျနော်တို့ချိတ်ဆက်စာရင်း၏ဒုတိယတစ်ဝက် reverse နှင့်ထို့နောက်သက်ဆိုင်ရာတန်ဖိုးများကိုတန်းတူရှိမရှိစစ်ဆေးနိုင်ရန်နှစ် ဦး စလုံးနှစ်ခုလုံးအတွက် forward ကြားမှာနှစ်ခုကိုအသုံးပြုပါ။ ဤလုပ်ငန်းစဉ်အတွက်ကျွန်ုပ်တို့သည် -

  • ဒုတိယတစ်ဝက်ကိုပြန်ပြောင်းနိုင်အောင်စာရင်းရဲ့အလယ်ကိုရှာပါ။
  • စာရင်း၏ဒုတိယတစ်ဝက်ကို reverse ရန် function ကိုဖန်တီးပါ
  • ပထမနှင့်ဒုတိယတစ်ဝက်သည်ညီမျှမှုရှိမရှိစစ်ဆေးပါ

အထက်ဖော်ပြပါအရာအားလုံးကို linear အချိန်တွင်လုပ်ဆောင်နိုင်သည်။ ကျနော်တို့လင့်ခ်လုပ်ထားတဲ့ list ကိုပြန်ပြင်ပြီးတဲ့နောက်ဒုတိယတစ်ဝက်မပြီးမချင်းစစ်ဆေးပါတယ်။

Palindrome Linked စာရင်း Leetcode ဖြေရှင်းချက်

algorithm

  1. If ဦးခေါင်း is တရားမဝင်သော:
    • ပြန်လာပါ
  2. သုံးပြီးချိတ်ဆက်စာရင်း၏အလယ်ကိုရှာပါ middleOfList (ဦးခေါင်းfunction ကို:
    • နှစ်ခုထောက်ပြ Initialize နှေးနှေး နှင့် လျင်မြန်စွာ နှစ် ဦး စလုံးစာရင်း၏ ဦး ခေါင်းကိုညွှန်ပြ
    • မှီတိုငျအောငျ မြန် နှင့် မြန်ဆန် နှစ်ခုလုံးက မဟုတ် တရားမဝင်သော
      1. တိုး နှေးနှေး ၂၀၂၂ ခုနှစ်တွင် နှေးကွေး = slow.next
      2. တိုး လျင်မြန်စွာ ၂၀၂၂ ခုနှစ်တွင် အစာရှောင်ခြင်း = fast.next.next
    • နှေးနှေး pointer ယခုစာရင်း၏အလယ်ကိုညွှန်ပြ
    • ပြန်လာ နှေးနှေး
  3. ယခုကျွန်ုပ်တို့သည်ခေါ်ဆိုမှု၏ဒုတိယတစ်ဝက်ကိုပြောင်းပြန်လုပ်သည် reverseList (ဦး ခေါင်း = အလယ်အလတ်) function ကို
    • ကန ဦး prev = တရားမဝင်သော
    • စဉ်တွင် ဦးခေါင်း null မဟုတ်ပါဘူး:
      • လာမယ့် node ကိုယာယီ variable ထဲမှာသိမ်းထားပါ လာမယ့်
      • အသုံးပြုခြင်းဖြင့် pointer ဦး တည်ချက်ကိုပြောင်းပါ head.next = prev
      • prev = ဦး ခေါင်း
      • သုံးပြီးစာရင်းထဲတွင်ရှေ့ဆက်ပါ head = နောက်
    • ပြန်လာ prev
  4. အခုတော့နှစ်ခုထောက်ပြ intialise ptr1 နှင့် ptr2 နှစ်ဖက်စလုံးကိုဖြတ်ပြီးကြားဖြတ်ရန်
    1. ptr1 = ဦး ခေါင်း
    2. ptr2 = စတင်ပါ ဒုတိယတစ်ဝက်၏
    3. စဉ်တွင် ptr2 null မဟုတ်ပါဘူး:
      1. if ptr1.အဘိုး ညီမျှသည်မဟုတ် ptr2.အဘိုး
        1. ပြန်လာ မမှန်သော
    4. ပြန်လာ စစ်မှန်တဲ့ ကျွန်တော်ပထမနှင့်ဒုတိယတစ်ဝက်တွင် node တိုင်းကိုစစ်ဆေးသည်
  5. ရလဒ်ပုံနှိပ်ပါ

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

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;
}

Java အစီအစဉ်

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

Palindrome Linked List Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ကျနော်တို့ linear loops တွေကိုသုံးတဲ့အခါ list ရဲ့အလယ်ကိုရှာပြီး၎င်းကိုပြန်ပြောင်းပါ။ ဒီမှာ, N = စာရင်း၏အရွယ်အစား။

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျွန်တော်သာစဉ်ဆက်မပြတ်အပိုအာကာသကိုသုံးပါအဖြစ်။