Palindrome المرتبطة قائمة Leetcode الحل  


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ عاصمة واحدة سيسكو Facebook جوجل انتزاع إنتل IXL Microsoft Nutanix أوراكل Paytm Snapchat اوبر ياندكس
خوارزميات الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions قائمة مرتبطة اثنين من المؤشرات

في مشكلة "قائمة Palindrome المرتبطة" ، علينا التحقق مما إذا كان هناك عدد صحيح فردي قائمة مرتبطة متناظرة أم لا.

مثال  

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 حل Leetcode

خوارزمية

  1. وظيفة isPalindrome () تُستخدم لإرجاع ما إذا كانت القائمة بها رئيس متناظرة أم لا
  2. نعلن عن عضو بيانات من الفئة المسمى جبهة لتخزين العقد لإعادة توجيه التكرارات
  3. In isPalindrom ():
    • تهيئة الجبهة = الرأس
    • عودة متناظرة
  4. In متناظرةتيار):
    • If تيار is فارغة:
      • عائد أعلى صحيح
    • If متناظرةالحالي) is زائف:
      • عائد أعلى زائف
    • If القيمة الحالية is ليس يساوي الجبهة. القيمة
      • عائد أعلى زائف
    • زيادة الجبهة على النحو التالي:
      • الجبهة = الجبهة
    • عائد أعلى صحيح حيث أجرينا جميع الفحوصات
  5. اطبع النتيجة

تنفيذ حل Leetcode قائمة 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 المرتبطة بحل Leetcode

تعقيد الوقت

على) كما نجتاز القائمة مرة واحدة باستخدام العودية. هنا ، N = عدد العقد في القائمة.

انظر أيضا
تسلسل الشجرة الثنائية وإلغاء تسلسلها

تعقيد الفضاء

على) كما نسمي دالة تكرارية للتحقق من إنشاء كل عقدة N كومة الإطارات في الذاكرة.

نهج (عكس النصف الآخر)  

الطريقة الوحيدة للتخلص من المساحة المستخدمة في العودية هي تعديل القائمة المحددة في المكان. نعكس النصف الثاني من القائمة المرتبطة ثم نستخدم مكررين للأمام لكلا النصفين للتحقق مما إذا كانت القيم المقابلة متساوية. لهذه العملية ، نحتاج إلى:

  • أوجد منتصف القائمة حتى نتمكن من عكس النصف الثاني.
  • قم بإنشاء دالة لعكس النصف الثاني من القائمة
  • تحقق مما إذا كان النصف الأول والثاني متساويين

يمكن القيام بكل ما سبق في وقت خطي بعد عكس القائمة المرتبطة ، نبدأ في التحقق حتى اكتمال الشوط الثاني.

Palindrome المرتبطة قائمة Leetcode الحل

خوارزمية

  1. If رئيس is فارغة:
    • عودة صحيح
  2. ابحث عن منتصف القائمة المرتبطة باستخدام MiddleOfList (رئيسوظيفة:
    • تهيئة مؤشرين بطيء و بسرعة كلاهما يشير إلى رأس القائمة
    • حتى سريع و سريع. التالي. التالي كلاهما ليس لا شيء:
      1. زيادة راتب بطيء بحلول عام 1، بطيء = بطيء
      2. زيادة راتب بسرعة بحلول عام 2، سريع = fast.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

تنفيذ حل 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 المرتبطة بحل Leetcode

تعقيد الوقت

على) عندما نستخدم الحلقات الخطية لإيجاد منتصف القائمة ، نعكسها ، ونقارن كلا النصفين. هنا، N = حجم القائمة.

انظر أيضا
الحد الأدنى من المقايضات المطلوبة لتجميع جميع العناصر الأقل من أو المساوية لـ k معًا

تعقيد الفضاء

يا (1) لأننا نستخدم مساحة إضافية ثابتة فقط.