Palindrome تړلي لیست لیټکوډ حل  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه د بلومبرګ پلازمیینه يو سیسکو فیسبوک د ګوګل ګراب Intel IXL د Microsoft نیوټنکس سينه_پوښ پیټم Snapchat über Yandex
الگوريتم کوډ ورکول مرکه د مرکې چمتووالی لیټ کوډ د لیټ کوډ حلونه تړلي لیست دوه نښې

د "پالینډروم تړل شوي لیست" ستونزه کې ، موږ باید وګورو چې ایا ورکړل شوي یووازی عدد دی تړلي لیست پالنډروم دی او که نه.

بېلګه  

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

پورته کوډ لومړی چاپ کوي پاتې په ونې کې نوډونه ځکه چې موږ په تکرار سره دا فنکشن ته غږ کوو چې پخپله د نوډ ارزښت چاپولو دمخه د هرې ریښې پاتې ماشومانو ته لاړ شي. په ورته ډول ، موږ وکاروو تکرار لومړی وروستي نوډونو ته لاړ شئ او کله چې فنکشن بیکریک شي ، نو موږ به په متناسب ترتیب کې د نوډ ارزښتونه ترلاسه کړو. موږ به د تکرار مخکي تغیر لپاره وکاروو کوم چې به د تکرار په واسطه غیر اغیزمن شي. پدې توګه ، موږ کولی شو د ایتراټور قیمت پرتله کړو او د عناصرو پرتله کولو لپاره تکرار سره ترلاسه شوي ریډ نوډ ارزښت.

هم وګوره
د IP پتې لیټکوډ حل حل کول

الګوریتم

  1. یو فنکشن isPalindrome () د بیرته راستنیدو لپاره کارول کیږي ایا لیست د سره سر پالنډروم دی او که نه
  2. موږ د نوم لاندې ټولګي د معلوماتو غړي اعلان کوو مخ د مخکې تکرار لپاره نوډونو ذخیره کول
  3. In isPalindrom ():
    • پېل کول مخ = سر
    • بیرته راستنیدونکی سر (سر)
  4. In پالنډروم چیک (اوسني):
    • If اوسني is مردود:
      • بېرته رښتيا
    • If پالنډروم چیک (اوسنی مخ) is غلط:
      • بېرته غلط
    • If اوسنی ارزښت is نه برابر دمخه. ارزښت
      • بېرته غلط
    • د مخ په زیاتیدونکي محاذ په توګه:
      • سامنے = مخکښ
    • بېرته رښتيا لکه څنګه چې موږ ټول چیکونه ترسره کړل
  5. پایله چاپ کړئ

د Palindrome تړل شوي لیست لیټکوډ حل پلي کول

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

جاوا پروګرام

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 تړل شوي لیټ لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N) لکه څنګه چې موږ یوځل د تکرار په کارولو سره لیست له مینځه وړو. دلته ، په لیست کې د N = شمیرو.

هم وګوره
د بائنری ونې سیرال کول او له منځه وړل

د ځای پیچلتیا

O (N) لکه څنګه چې موږ د تکراري فنکشن غږ کوو چې د هرې نوډ رامینځته کولو لپاره چک وکړي N په حافظه کې چوکاټونه.

کړنلاره (د نورو نیمایي برعکس)  

په تکرار کې کارول شوي ځای څخه د خلاصون یوازینۍ لار په ځای کې ورکړل شوي لیست کې اصلاح کول دي. موږ د تړل شوي لیست دوهمه نیمه بیرته واړوو او بیا د دوه برخې لپاره دوه مخکیني تکرارونکي کاروو ترڅو وکتل شي چې ایا اړونده ارزښتونه مساوي دي. د دې پروسې لپاره ، موږ اړتیا لرو:

  • د لیست منځنۍ برخه ومومئ ترڅو موږ وکولی شو دوهمه نیمه بیرته واړوو.
  • د لیست دوهم نیمایي برعکس کولو لپاره یو فنکشن جوړ کړئ
  • وګوره چې لومړی او دوهمه نیمه مساوي دي

ټول پورتني ټول په خطي وخت کې ترسره کیدی شي. وروسته له هغه چې موږ تړلي لیست بیرته واړوو ، موږ د دویمې نیمایې بشپړیدو پورې چک کول پیل کوو.

Palindrome تړلي لیست لیټکوډ حلقید

الګوریتم

  1. If سر is مردود:
    • ریښتنی راستنیدل
  2. په کارولو سره د تړلي لیست منځنۍ برخه ومومئ منځنۍ افلاس (سرفعالیت:
    • دوه نښې پیل کړئ ورو او روژه دواړه د لیست سر ته ګوته نیسي
    • تر فاسټ.ینکسټ او quick.next.next دواړه دي نه باطل:
      1. زیاتوالی ورو په 1 کې ، ورو = ورو.next
      2. زیاتوالی روژه په 2 کې ، چټک = quick.next.next
    • ورو پوائنټر اوس د لیست مینځ ته اشاره کوي
    • بېرته ورو
  3. اوس موږ د لیست زنګ دوهم نیمایي ته بیرته اړوو ریورس لیست (سر = منځمهاله) دنده
    • پیل کول مخکې = مردود
    • په داسې حال کې سر باطل نه دی:
      • راتلونکی نوډ په لنډمهاله متغیر کې زیرمه کړئ ، لکه بل
      • د کارولو پواسطه د شا ته لور وګرځوئ Head.next = prev
      • prev = سر
      • په کارولو سره په لیست کې مخکې حرکت وکړئ سر = بل
    • بېرته مخکې
  4. اوس ، دوه نښې په ګوته کړئ ptr1 او ptr2 په دواړو برخو کې تکراریدل:
    1. ptr1 = سر
    2. ptr2 = پیل د دوهم نیمایی
    3. په داسې حال کې ptr2 باطل نه دی:
      1. if ptr1.ارزښت سره مساوي ندي ptr2.ارزښت
        1. بېرته غلط
    4. بېرته رښتيا لکه څنګه چې موږ هر نوډ په لومړي او دوهم نیم کې چیک کړ
  5. پایله چاپ کړئ
هم وګوره
د K خالی ځایونه LeetCode

د Palindrome تړل شوي لیست لیټکوډ حل پلي کول

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

جاوا پروګرام

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 تړل شوي لیټ لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N) لکه څنګه چې موږ د لیست په مینځ کې موندلو لپاره لاین لوپونه کاروو ، بیرته یې واړوو ، او دواړه برخې نیمه کړو. دلته، N = د لیست کچه.

هم وګوره
لږترلږه بدلونونه اړین دي چې ټول عناصر له k څخه لږ یا مساوي راوړي

د ځای پیچلتیا

O (1) لکه څنګه چې موږ یوازې دوامداره اضافي ځای کاروو.