פתרון Leetcode של רשימת קישורים לפלינדרום


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג קפיטל אחד סיסקו פייסבוק Google קבר אינטל IXL מיקרוסופט נוטניקס אורקל Paytm Snapchat סופר 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);
}

הקוד לעיל מודפס לראשונה עזבו צמתים בעץ מכיוון שאנחנו מכנים רקורסיבית את הפונקציה ללכת לילדים שמאליים מכל שורש לפני שמדפיסים את ערך הצומת עצמו. באופן דומה, אנו יכולים להשתמש רקורסיה כדי לעבור קודם לצמתים האחרונים וכאשר הפונקציה תחזור אחורה, נקבל את ערכי הצומת בסדר הפוך. נשתמש במשתנה כדי לחזור על קדימה אשר לא יושפע מהרקורס. באופן זה, אנו יכולים להשוות בין ערך איטרטור קדימה לבין ערך צומת הפוך המתקבל על ידי רקורסיה כדי להשוות אלמנטים.

אַלגוֹרִיתְם

  1. תפקוד isPalindrome () משמש להחזרת האם רשימה עם ראש הוא פלינדרום או לא
  2. אנו מצהירים כי חבר הנתונים בכיתה נקרא בשם חזית לאחסן צמתים לאיטרציות קדימה
  3. In isPalindrom ():
    • אתחל קדמי = ראש
    • חזרה לפלינדרום בדוק (ראש)
  4. In palindromeCheck (נוֹכְחִי):
    • If נוֹכְחִי is ריק:
      • לַחֲזוֹר נכון
    • If palindromeCheck (הנוכחי. הבא) is שקר:
      • לַחֲזוֹר שקר
    • If ערך נוכחי is לֹא שווה ל חזית.ערך
      • לַחֲזוֹר שקר
    • תוספת חזית כמו:
      • חזית = חזית.באחריה
    • לַחֲזוֹר נכון כשביצענו את כל הבדיקות
  5. הדפיס את התוצאה

יישום פתרון 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

ניתוח מורכבות של פתרון Leetcode ברשימה המקושרת לפלינדרום

מורכבות זמן

עַל) כשאנחנו חוצים את הרשימה פעם אחת באמצעות רקורסיה. הנה, N = מספר הצמתים ברשימה.

מורכבות בחלל

עַל) כפי שאנו מכנים פונקציה רקורסיבית כדי לבדוק אם נוצר כל צומת N ערימת מסגרות בזיכרון.

גישה (הפוך חצי אחר)

הדרך היחידה להיפטר מהשטח המשמש ברקורסיה היא לשנות את הרשימה הנתונה במקום. אנו הופכים את המחצית השנייה של הרשימה המקושרת ואז משתמשים בשני איטרטורים קדימה לשני החצאים כדי לבדוק אם הערכים המתאימים שווים. לתהליך זה עלינו:

  • מצא את אמצע הרשימה כדי שנוכל להפוך את המחצית השנייה.
  • צור פונקציה כדי להפוך את המחצית השנייה של הרשימה
  • בדוק אם המחצית הראשונה והשנייה שוות

כל האמור לעיל יכול להיעשות בזמן ליניארי. לאחר שנפוך את הרשימה המקושרת, אנו מתחילים לבדוק עד שהמחצית השנייה תסתיים.

פתרון Leetcode של רשימת קישורים לפלינדרום

אַלגוֹרִיתְם

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

יישום פתרון 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

ניתוח מורכבות של פתרון Leetcode ברשימה המקושרת לפלינדרום

מורכבות זמן

עַל) כאשר אנו משתמשים בלולאות ליניאריות כדי למצוא את אמצע הרשימה, להפוך אותה ולהשוות את שני החצאים. פה, N = גודל הרשימה.

מורכבות בחלל

O (1) כיוון שאנו משתמשים רק בתוספת שטח קבועה.