Palindrome- თან დაკავშირებული ლინეტების კოდი


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg Capital One Cisco Facebook Google Grave Intel IXL microsoft ნუტუნიქსი Oracle Paytm Snapchat Uber Yandex
მიბმული სია ორი მაჩვენებელი

პრობლემში ”Palindrome Linked List”, ჩვენ უნდა გადავამოწმოთ, მოცემულია ცალკე მთელი რიცხვი დაკავშირებული სია არის პალინდრომი თუ არა.

მაგალითი

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

განმარტება # 1: სია არის პალინდრომი, რადგან ყველა ელემენტი დასაწყისიდან და უკან იგივეა მნიშვნელობით.

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

განმარტება # 2: სია არ არის პალინდრომი, რადგან ელემენტები უკან და უკან არ არის იგივე.

მიდგომა (Recursion)

ადვილი შესამჩნევია, რომ მასივის უკანა მხრიდან გვჭირდება კვანძების დეტალები პალინდრომის თვისებების შესამოწმებლად. ამ შემთხვევაში, ჩვენ გვაქვს ცალკე დაკავშირებული სია ნიშნავს, რომ მხოლოდ განმეორებითი განმეორება შეგვიძლია ნებისმიერი კვანძის მისაღწევად. ამრიგად, მნიშვნელოვანი ხდება მონაცემთა გარკვეული სტრუქტურის გამოყენება კვანძების უკანა მხრიდან დასაკავებლად, მაგ დასტის არის შესაძლო ვარიანტი, რადგან ის ინახავს უახლეს კვანძს ზედა ნაწილში. შეგვიძლია ანალოგიურად გამოვიყენოთ რეკურსიც. რეკურსია არის ელეგანტური, რომ კვანძის მნიშვნელობებს საპირისპირო თანმიმდევრობით მივიღოთ. განვიხილოთ ქვემოთ მოცემული ზოგადი ფსევდოკოდი უკეთესად გასაგებად:

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

ზემოთ მოცემული კოდი პირველად ბეჭდავს დარჩა კვანძების ხე, რადგან ჩვენ რეკურსიულად მოვუწოდებთ ფუნქცია წასვლა მარცხენა ბავშვები ნებისმიერი root სანამ ბეჭდვის ღირებულება თავად კვანძის. ანალოგიურად, ჩვენ შეგვიძლია გამოვიყენოთ რეკურსია პირველ რიგში ბოლო კვანძებში გადასასვლელად და როდესაც ფუნქცია უკან დაიხევს, კვანძის მნიშვნელობებს საპირისპირო თანმიმდევრობით მივიღებთ. ჩვენ ვიყენებთ ცვლადს წინსვლის განმეორებით, რაც გავლენას არ მოახდენს რეკურსის გავლენით. ამ გზით, ჩვენ შეგვიძლია შევადაროთ განმეორებითი მნიშვნელობის iterator და საპირისპირო კვანძის მნიშვნელობა, რომელიც მიღებულია რეკურსიით, ელემენტების შედარების მიზნით.

ალგორითმი

  1. ფუნქცია isPalindrome () გამოიყენება სიის დასაბრუნებლად უფროსი არის პალინდრომი თუ არა
  2. ჩვენ ვაცხადებთ კლასის მონაცემების წევრს სახელწოდებით წინა კვანძების შესანახად გადამისამართება
  3. In isPalindrom ():
    • ინიციალიზაცია წინა = თავი
    • დაბრუნება palindromeCheck (ხელმძღვანელი)
  4. In palindromeCheck (მიმდინარე):
    • If მიმდინარე is null:
      • დაბრუნების მართალია
    • If palindromeCheck (მიმდინარე. შემდეგი) is ყალბი:
      • დაბრუნების ყალბი
    • If მიმდინარე. ღირებულება is არ ტოლია წინა. ღირებულება
      • დაბრუნების ყალბი
    • ნამატი წინა, როგორც:
      • წინა = წინა. შემდეგი
    • დაბრუნების მართალია როგორც ჩვენ ყველა შემოწმება შევასრულეთ
  5. დაბეჭდე შედეგი

Palindrome Linked List Leetcode Solution- ის განხორციელება

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 Solution- ის სირთულის ანალიზი

დროის სირთულე

O (N) როგორც ჩვენ ვხედავთ სიას ერთხელ, რეკურსის გამოყენებით. აქ, N = კვანძების რაოდენობა სიაში.

სივრცის სირთულე

O (N) როგორც რეკურსიულ ფუნქციას ვუწოდებთ, შეამოწმოს თითოეული კვანძის შექმნა N დასტის ჩარჩოები მეხსიერებაში.

მიდგომა (უკუ სხვა ნახევარი)

რეკურსიაში გამოყენებული სივრცის მოშორების ერთადერთი გზაა მოცემული ჩამონათვალის ადგილზე შეცვლა. ჩვენ უკავშირდებით დაკავშირებული სიის მეორე ნახევარს და შემდეგ ვიყენებთ ორი განმეორებით განმეორებას ორივე ნაწილისთვის, რათა შეამოწმოთ შესაბამისი მნიშვნელობები ტოლია. ამ პროცესისთვის საჭიროა:

  • იპოვნეთ სიის შუაში, რომ მეორე ნახევრის შეცვლა შეგვიძლია.
  • ფუნქციის შექმნა სიის მეორე ნახევრის საპირისპიროდ
  • შეამოწმეთ ტოლია თუ არა პირველი და მეორე ნახევარი

ყოველივე ზემოთქმული შეიძლება გაკეთდეს სწორხაზოვან დროში. მას შემდეგ, რაც უკავშირდება დაკავშირებული სია, ვიწყებთ შემოწმებას მეორე ნახევრის დასრულებამდე.

Palindrome- თან დაკავშირებული ლინეტების კოდი

ალგორითმი

  1. If უფროსი is null:
    • ნამდვილი დაბრუნება
  2. იპოვნეთ დაკავშირებული სიის შუა რიცხვებით middleOfList (უფროსიფუნქცია:
    • ორი მაჩვენებლის ინიცირება ნელი და სწრაფი ორივე მიუთითებს სიის თავზე
    • მანამდე სწრაფი. შემდეგი და სწრაფი. შემდეგი. შემდეგი ორივე არ null:
      1. ზრდა ნელი 1 წლისთვის ნელი = ნელი. შემდეგი
      2. ზრდა სწრაფი 2 წლისთვის სწრაფი = სწრაფი. შემდეგი. შემდეგი
    • ნელი მაჩვენებელი ახლა მიუთითებს სიის შუაზე
    • დაბრუნების ნელი
  3. ახლა ჩვენ უკუვაგდებთ სიის მეორე ნახევარს საპირისპირო სია (ხელმძღვანელი = შუა. შემდეგი) ფუნქცია
    • ინიციალიზაცია წინა = null
    • ხოლო უფროსი არ არის ნულოვანი:
      • შეინახეთ შემდეგი კვანძი დროებით ცვლადში, შემდეგი
      • საჩვენებელი მიმართულების შეცვლა გამოყენებით თავი. შემდეგი = წინა
      • პრევ = თავი
      • გადადით სიაში გამოყენებით თავი = ​​შემდეგი
    • დაბრუნების წინა
  4. ახლავე გაითვალისწინეთ ორი მაჩვენებელი ptr1 და ptr2 განმეორება ორივე ნახევრის მეშვეობით:
    1. ptr1 = თავი
    2. ptr2 = დაწყება მეორე ნახევრის
    3. ხოლო ptr2 არ არის ნულოვანი:
      1. if ptr1.ღირებულება ტოლი არ არის ptr2.ღირებულება
        1. დაბრუნების ყალბი
    4. დაბრუნების მართალია როგორც ჩვენ გადავამოწმეთ ყველა კვანძი პირველ და მეორე ნახევარში
  5. დაბეჭდე შედეგი

Palindrome Linked List Leetcode Solution- ის განხორციელება

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 Solution- ის სირთულის ანალიზი

დროის სირთულე

O (N) ვიყენებთ ხაზობრივ მარყუჟებს სიის შუა ნაწილის მოსაძებნად, მისი უკუქცევით და შედარების ორივე ნახევრისთვის. Აქ, N = სიის ზომა.

სივრცის სირთულე

O (1) რადგან ჩვენ ვიყენებთ მხოლოდ მუდმივ დამატებით ადგილს.