Λύση Leetcode λίστας συνδεδεμένων με Palindrome


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg Capital One Cisco Facebook Google Αρπάξτε Intel IXL Microsoft Nutanix μαντείο Paytm Snapchat Uber Yandex
Συνδεδεμένη λίστα Δύο δείκτες

Στο πρόβλημα "Λίστα συνδέσμου Palindrome", πρέπει να ελέγξουμε εάν ένας δεδομένος μοναδικός ακέραιος συνδεδεμένη λίστα είναι παλινδρόμηση ή όχι.

Παράδειγμα

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

Επεξήγηση # 1: Η λίστα είναι palindrome καθώς όλα τα στοιχεία από την αρχή και την πίσω έχουν την ίδια αξία.

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

Επεξήγηση # 2: Η λίστα δεν είναι palindrome καθώς τα στοιχεία από πίσω και πίσω δεν είναι τα ίδια.

Πλησιάζω(Αναδρομή)

Αυτό είναι εύκολο να παρατηρηθεί ότι πρέπει να έχουμε τις λεπτομέρειες των κόμβων από το πίσω μέρος του πίνακα για τον έλεγχο ιδιοτήτων palindrome. Σε αυτήν την περίπτωση, έχουμε ένα χωριστά συνδεδεμένη λίστα που σημαίνει ότι μπορούμε μόνο να προχωρήσουμε προς τα εμπρός για να φτάσουμε σε οποιονδήποτε κόμβο. Έτσι, καθίσταται σημαντικό να χρησιμοποιήσετε κάποια δομή δεδομένων για να κρατήσετε τους κόμβους από το πίσω μέρος, π.χ. σωρός είναι μια πιθανή επιλογή καθώς διατηρεί τον πιο πρόσφατο κόμβο στην κορυφή. Μπορούμε επίσης να χρησιμοποιήσουμε την αναδρομή με παρόμοιο τρόπο. Η επανάληψη είναι κομψή για να πάρει τις τιμές των κόμβων σε αντίστροφη σειρά. Εξετάστε τον παρακάτω γενικό ψευδοκώδικα για καλύτερη κατανόηση:

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

Εκτυπώνεται πρώτα ο παραπάνω κωδικός αριστερά κόμβοι στο δέντρο επειδή καλούμε αναδρομικά τη συνάρτηση για να μεταβείτε στα αριστερά παιδιά οποιασδήποτε ρίζας πριν εκτυπώσετε την ίδια την τιμή του κόμβου. Ομοίως, μπορούμε να χρησιμοποιήσουμε αναδρομή για να μεταβείτε πρώτα στους τελευταίους κόμβους και όταν η συνάρτηση θα ακολουθήσει, θα λάβουμε τις τιμές των κόμβων με αντίστροφη σειρά. Θα χρησιμοποιήσουμε μια μεταβλητή για να επαναλάβουμε την προώθηση που δεν θα επηρεαστεί από την επανάληψη. Με αυτόν τον τρόπο, μπορούμε να συγκρίνουμε την τιμή του επαναληπτικού προς τα εμπρός και την τιμή του αντίστροφου κόμβου που λαμβάνεται με την επανάληψη για τη σύγκριση στοιχείων.

Αλγόριθμος

  1. Μια συνάρτηση isPalindrome () χρησιμοποιείται για να επιστρέψει εάν μια λίστα με κεφάλι είναι palindrome ή όχι
  2. Δηλώνουμε ένα μέλος της κατηγορίας με όνομα εμπρός για αποθήκευση κόμβων για επαναλαμβανόμενες επαναλήψεις
  3. In isPalindrom ():
    • αρχικοποίηση μπροστά = κεφάλι
    • επιστροφή palindromeCheck (κεφάλι)
  4. In palindromeΕλέγξτε (ρεύμα):
    • If ρεύμα is μηδέν:
      • απόδοση αληθής
    • If palindromeΕλέγξτε (current.next) is ψευδής:
      • απόδοση ψευδής
    • If τρέχουσα τιμή is δεν ίσο με front.value
      • απόδοση ψευδής
    • προσαύξηση ως:
      • εμπρός = εμπρός. επόμενο
    • απόδοση αληθής καθώς πραγματοποιήσαμε όλους τους ελέγχους
  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;
}

Πρόγραμμα 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 συνδεδεμένης λίστας Palindrome

Χρόνος πολυπλοκότητας

ΕΠΙ) καθώς διασχίζουμε τη λίστα χρησιμοποιώντας μια επανάληψη. Εδώ, N = αριθμός κόμβων στη λίστα.

Διαστημική πολυπλοκότητα

ΕΠΙ) καθώς καλούμε μια αναδρομική συνάρτηση για έλεγχο κάθε δημιουργίας κόμβου N στοίβα καρέ στη μνήμη.

Προσέγγιση (Αντίστροφο άλλο μισό)

Ο μόνος τρόπος για να απαλλαγείτε από το χώρο που χρησιμοποιείται στην αναδρομή είναι να τροποποιήσετε τη δεδομένη λίστα επιτόπου. Αντιστρέψουμε το δεύτερο μισό της συνδεδεμένης λίστας και στη συνέχεια χρησιμοποιούμε δύο επαναλαμβανόμενες επαναλήψεις και για τα δύο μισά για να ελέγξουμε εάν οι αντίστοιχες τιμές είναι ίσες. Για αυτήν τη διαδικασία, πρέπει:

  • βρείτε τη μέση της λίστας, ώστε να αντιστρέψουμε το δεύτερο ημίχρονο.
  • δημιουργήστε μια συνάρτηση για να αντιστρέψετε το δεύτερο μισό της λίστας
  • ελέγξτε αν το πρώτο και το δεύτερο ημίχρονο είναι ίσο

Όλα τα παραπάνω μπορούν να γίνουν σε γραμμικό χρόνο. Αφού αντιστρέψουμε τη συνδεδεμένη λίστα, αρχίζουμε να ελέγχουμε μέχρι να ολοκληρωθεί το δεύτερο ημίχρονο.

Λύση Leetcode λίστας συνδεδεμένων με Palindrome

Αλγόριθμος

  1. If κεφάλι is μηδέν:
    • επιστροφή true
  2. Βρείτε τη μέση της συνδεδεμένης λίστας χρησιμοποιώντας middleOfList (κεφάλιλειτουργία:
    • Αρχικοποιήστε δύο δείκτες επιβραδύνουν γρήγορα και οι δύο δείχνουν προς το κεφάλι της λίστας
    • Μέχρι fast.next fast.next.next είναι και τα δύο δεν μηδενικό:
      1. Αύξηση επιβραδύνουν έως το 1, αργή = αργή. επόμενη
      2. Αύξηση γρήγορα έως το 2, fast = fast.next.next
    • επιβραδύνουν ο δείκτης δείχνει τώρα στη μέση της λίστας
    • απόδοση επιβραδύνουν
  3. Τώρα αντιστρέφουμε το δεύτερο μισό της κλήσης λίστας reverseList (κεφαλή = mid.next) λειτουργία
    • Αρχικοποίηση prev = μηδέν
    • ενώ κεφάλι δεν είναι μηδενικό:
      • Αποθηκεύστε τον επόμενο κόμβο σε μια προσωρινή μεταβλητή, ως επόμενη
      • Αντιστρέψτε την κατεύθυνση του δείκτη χρησιμοποιώντας head.next = prev
      • prev = κεφάλι
      • Προχωρήστε στη λίστα χρησιμοποιώντας κεφάλι = επόμενο
    • απόδοση prev
  4. Τώρα, εκφωνήστε δύο δείκτες ptr1 ptr2 για επανάληψη και στα δύο μισά:
    1. ptr1 = κεφάλι
    2. ptr2 = έναρξη του δευτέρου ημιχρόνου
    3. ενώ ptr2 δεν είναι μηδενικό:
      1. if ptr1.αξία δεν είναι ίσο με ptr2.αξία
        1. απόδοση ψευδής
    4. απόδοση αληθής καθώς ελέγχαμε κάθε κόμβο στο πρώτο και δεύτερο ημίχρονο
  5. Εκτυπώστε το αποτέλεσμα

Υλοποίηση Λύσης 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;
}

Πρόγραμμα 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 συνδεδεμένης λίστας Palindrome

Χρόνος πολυπλοκότητας

ΕΠΙ) καθώς χρησιμοποιούμε γραμμικούς βρόχους για να βρούμε τη μέση της λίστας, να την αντιστρέψουμε και να συγκρίνουμε και τα δύο μισά. Εδώ, N = μέγεθος της λίστας.

Διαστημική πολυπλοκότητα

Ο (1) καθώς χρησιμοποιούμε μόνο σταθερό επιπλέον χώρο.