פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג Capital One סיסקאָ facebook גוגל ערנסט ינטעל IXL מייקראָסאָפֿט נוטאַניקס אָראַקל Paytm Snapchat ובער יאַנדעקס
לינקעד-רשימה צוויי פּאָינטערס

אין דעם פּראָבלעם "פּאַלינדראָמע לינקעד רשימה", מיר האָבן צו קאָנטראָלירן צי אַ געגעבן יינציק גאַנץ נומער לינגקט רשימה איז אַ פּאַלינדראָמע אָדער נישט.

בייַשפּיל

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

דערקלערונג # 1: די רשימה איז פּאַלינדראָום ווייַל אַלע יסודות פון די אָנהייב און צוריק זענען די זעלבע אין ווערט.

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

דערקלערונג # 2: די רשימה איז נישט פּאַלינדראָום, ווייַל עלעמענטן פֿון צוריק און אַרויס זענען נישט די זעלבע.

צוגאַנג (רעקורסיאָן)

דאָס איז גרינג צו באַמערקן אַז מיר דאַרפֿן צו האָבן די דעטאַילס פון די נאָודז פֿון די צוריק פון די מענגע פֿאַר קאָנטראָלירונג פון פּאַלינדראָמע פּראָפּערטיעס. אין דעם פאַל, מיר האָבן אַ יינציק לינגקט רשימה טייַטש אַז מיר קענען נאָר יבערקערן פאָרויס צו דערגרייכן קיין נאָדע. דעריבער, עס איז וויכטיק צו נוצן עטלעכע דאַטן סטרוקטור צו האַלטן די נאָודז פֿון די צוריק, למשל stack איז אַ מעגלעך אָפּציע ווייַל עס האלט די לעצטע נאָדע אין די שפּיץ. מיר קענען אויך נוצן רעקורסיאָן סימילאַרלי. רעקורסיאָן איז אַן עלעגאַנט צו באַקומען די נאָדע וואַלועס אין פאַרקערט סדר. באַטראַכטן די אונטן אַלגעמיין פּסעודאָקאָדע פֿאַר בעסער פארשטאנד:

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

די אויבן קאָד פּרינץ ערשטער לינקס נאָודז אין דעם בוים ווייַל מיר רעקורסיוועלי רופן די פֿונקציע צו גיין צו לינקס קינדער פון קיין וואָרצל איידער דרוקן די ווערט פון די נאָדע זיך. סימילאַרלי, מיר קענען נוצן רעקורסיאָן צו גיין צו די לעצטע נאָודז ערשטער און ווען די פֿונקציע וועט צוריקציען, מיר וועלן באַקומען די נאָדע וואַלועס אין פאַרקערט סדר. מיר וועלן נוצן אַ בייַטעוודיק צו יבערקוקן פאָרויס וואָס וועט זיין אַנאַפעקטיד דורך רעקורסיאָן. אויף דעם וועג, מיר קענען פאַרגלייכן די ווערט פון יטעראַטאָר און די פאַרקערט נאָדע ווערט באקומען דורך רעקורסיאָן צו פאַרגלייכן עלעמענטן.

אַלגאָריטהם

  1. א פונקציע יספּאַלינדראָמע () איז געניצט צו צוריקקומען צי אַ רשימה מיט קאָפּ איז פּאַלינדראָמע אָדער נישט
  2. מיר דערקלערן אַ דאַטן מיטגליד פון דער קלאַס געהייסן פראָנט צו קראָם נאָודז פֿאַר פאָרויס יטעריישאַנז
  3. In יספּאַלינדראָם ():
    • Initialize פראָנט = קאָפּ
    • צוריקקומען פּאַלינדראָמע טשעק (קאָפּ)
  4. In פּאַלינדראָמע טשעק (קראַנט):
    • If קראַנט is נאַל:
      • צוריקקומען ריכטיק
    • If פּאַלינדראָמע טשעק (current.next) is פאַלש:
      • צוריקקומען פאַלש
    • If קראַנט. ווערט is טאָן גלייך צו פראָנט. ווערט
      • צוריקקומען פאַלש
    • ינקראַמאַנט פראָנט ווי:
      • פראָנט = פראָנט.נעסט
    • צוריקקומען ריכטיק ווי מיר דורכגעקאָכט אַלע די טשעקס
  5. דרוק דעם רעזולטאַט

ימפּלעמענטאַטיאָן פון פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס פון פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N) ווען מיר אַריבער די רשימה אַמאָל ניצן רעקורסיאָן. דאָ, N = נומער פון נאָודז אין דער רשימה.

ספעיס קאַמפּלעקסיטי

אָ (N) ווי מיר רופן אַ רעקורסיווע פונקציע צו קאָנטראָלירן פֿאַר יעדער נאָדע קריייטינג N אָנלייגן ראָמען אין דער זכּרון.

צוגאַנג (פאַרקערט אנדערע האַלב)

דער בלויז וועג צו באַפרייַען די פּלאַץ געניצט אין רעקורסיאָן איז צו מאָדיפיצירן די געגעבן רשימה אין-אָרט. מיר פאַרקערט די רגע האַלב פון די לינגקט רשימה און נוצן צוויי פאָרויס יטעראַטאָרס פֿאַר ביידע כאַווז צו קאָנטראָלירן אויב די קאָראַספּאַנדינג וואַלועס זענען גלייַך. פֿאַר דעם פּראָצעס, מיר דאַרפֿן צו:

  • געפֿינען די מיטל פון דער רשימה אַזוי אַז מיר קענען פאַרקערט די רגע האַלב.
  • שאַפֿן אַ פונקציע צו פאַרקערט די רגע האַלב פון די רשימה
  • קאָנטראָלירן אויב דער ערשטער און רגע האַלב זענען גלייַך

אַלע די אויבן קענען זיין געטאן אין לינעאַר צייט. נאָך פאַרקערט די לינגקט רשימה, מיר אָנהייבן קאָנטראָלירונג ביז די רגע האַלב געענדיקט.

פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן

אַלגאָריטהם

  1. If קאָפּ is נאַל:
    • צוריקקומען אמת
  2. געפֿינען די מיטל פון די לינגקט רשימה ניצן middleOfList (קאָפּפֿונקציע:
    • יניטיאַליזירן צוויי פּוינטערז פּאַמעלעך און פעסט ביידע אָנווייַזן צו די קאָפּ פון די רשימה
    • ביז פאַסט.נעקסט און fast.next.next זענען ביידע טאָן נול:
      1. Increment פּאַמעלעך דורך 1, פּאַמעלעך = פּאַמעלעך
      2. Increment פעסט דורך 2, שנעל = פאַסט.נעקסט.נעקסט
    • פּאַמעלעך טייַטל איצט ווייזט צו די מיטל פון דער רשימה
    • צוריקקומען פּאַמעלעך
  3. איצט מיר פאַרקערט די רגע האַלב פון די רשימה ריווערסליסט (קאָפּ = מיטל.עקסט) פונקציאָנירן
    • ערשט פריער = נאַל
    • ווייַלע קאָפּ איז נישט נול:
      • קראָם ווייַטער נאָדע אין אַ צייַטווייַליק בייַטעוודיק, ווי ווייַטער
      • פאַרקערט די טייַטל ריכטונג דורך ניצן head.next = פריער
      • פּריוו = קאָפּ
      • מאַך פאָרויס אין דער רשימה ניצן קאָפּ = ווייטער
    • צוריקקומען פריער
  4. איצט, ינטאַליזירן צוויי פּוינטערז פּטר 1 און פּטר 2 צו יטערירן דורך ביידע כאַווז:
    1. פּטר 1 = קאָפּ
    2. פּטר 2 = אָנהייב פון צווייטן העלפט
    3. ווייַלע פּטר 2 איז נישט נול:
      1. if פּטר 1.ווערט איז נישט גלייך צו פּטר 2.ווערט
        1. צוריקקומען פאַלש
    4. צוריקקומען ריכטיק ווי מיר אָפּגעשטעלט יעדער נאָדע אין דער ערשטער און רגע האַלב
  5. דרוק דעם רעזולטאַט

ימפּלעמענטאַטיאָן פון פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס פון פּאַלינדראָמע לינקעד רשימה לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N) ווען מיר נוצן לינעאַר לופּס צו געפֿינען די מיטל פון דער רשימה, פאַרקערט עס און פאַרגלייכן ביידע כאַווז. דאָ, N = גרייס פון דער רשימה.

ספעיס קאַמפּלעקסיטי

אָ (1) ווי מיר נוצן בלויז קעסיידערדיק עקסטרע פּלאַץ.