Κατάργηση Λύσης Leetcode Στοιχεία Συνδεδεμένης Λίστας  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg Capital One Facebook Google Microsoft
αλγόριθμοι κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions Συνδεδεμένη λίστα Καθαρή αποθήκευση

Δήλωση προβλήματος  

Σε αυτό το πρόβλημα, μας δίνεται μια σύνδεση λίστα με τους κόμβους του να έχουν ακέραιες τιμές. Πρέπει να διαγράψουμε μερικούς κόμβους από τη λίστα που έχουν τιμή ίση με βαλ. Το πρόβλημα δεν χρειάζεται να λυθεί στη θέση αλλά θα συζητήσουμε μια τέτοια προσέγγιση.

Παράδειγμα

List = 1 -> 2 -> 2 -> 3 -> 4 , val = 2
1 3 4
List = 2 -> 2 -> 2 -> 2 , val = 2
Empty List

Κατάργηση Λύσης Leetcode Στοιχεία Συνδεδεμένης Λίστας  

Προσέγγιση (Αναδρομική)  

Μπορούμε να καλέσουμε αναδρομικά την ίδια λειτουργία για να επιστρέψουμε το κεφάλι της απαιτούμενης λίστας. Αυτό επιτυγχάνεται καλώντας τη συνάρτηση στα επόμενα επιθήματα της συγκεκριμένης λίστας με ορισμένες προϋποθέσεις. Ωστόσο, πρέπει να χειριστούμε τη βασική θήκη όταν η λίστα είναι κενή. Υπάρχει μόνο μία ειδική περίπτωση:

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

Υλοποίηση Λύσης Leetcode Στοιχεία λίστας συνδεδεμένων λιστών

Πρόγραμμα C ++

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    if(head == NULL) {
        return head;
    }
    if(head->value == val) {
        listNode* temp = head->next;
        head->next = NULL;
        delete(head);
        return removeElements(temp , val);
    }

    head->next = removeElements(head->next , val);
    return head;
}

int main() {
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(2);
    head->next->next->next = new listNode(3);
    head->next->next->next->next = new listNode(4);

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

Πρόγραμμα Java

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
};

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
            return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        if(head == null) {
            return head;
        }
        if(head.value == val) {
            return removeElements(head.next , val);
        }

        head.next = removeElements(head.next , val);
        return head;
    }

    public static void main(String args[]) {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(2);
        head.next.next.next = new listNode(3);
        head.next.next.next.next = new listNode(4);

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

Ανάλυση πολυπλοκότητας του αριθμού συμπληρώματος Leetcode Solution

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

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

Βλέπε επίσης
Flood Fill LeetCode

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

Ο (1). Όπως ακολουθεί ο κωδικός υποτροπή ουράς.

Προσέγγιση (Επαναληπτική)  

Για να διαγράψουμε οποιονδήποτε κόμβο, πρέπει να έχουμε τη διεύθυνση του προηγούμενου κόμβου του, ώστε να μπορούμε να κάνουμε το προηγούμενο σημείο στο επόμενο. Αυτό δίνει μια ιδέα να διατηρηθεί ένα προηγούμενος δείκτη που θα μας βοηθήσει να χειριστούμε δείκτες στη λίστα. Τώρα, το σημαντικό σημείο είναι ότι ο πρώτος κόμβος στη λίστα δεν έχει προηγούμενο κόμβο. Επομένως, πρέπει να προσθέσουμε έναν κόμβο φρουρού στην αρχή της λίστας. Τώρα, μπορούμε να διασχίσουμε τον πρώτο κόμβο στη λίστα (κόμβος δίπλα στον κόμβο του φρουρού) και θα αντιμετωπίσουμε τις ακόλουθες δύο συνθήκες:

1.) node-> value == val: Σε αυτήν την περίπτωση, θα ορίσουμε prev-> next = κόμβος-> επόμενο. Αυτό θα συνδέσει τον προηγούμενο του τρέχοντος κόμβου με τον επόμενο του τρέχοντος κόμβου και θα διαγράψει τον τρέχοντα κόμβο χρησιμοποιώντας: διαγραφή (currentNode)

2.) Διαφορετικά, απλά ρυθμίσαμε prev = κεφάλι για επερχόμενους κόμβους.

Στο τέλος, η επόμενη λίστα είναι η απαιτούμενη λίστα.

Υλοποίηση Λύσης Leetcode Στοιχεία λίστας συνδεδεμένων λιστών

Πρόγραμμα C ++

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    listNode *dummy = new listNode(-1) , *prev = dummy , *toDelete;
    dummy->next = head;

    while(head != NULL) {
        if(head->value == val) {
            toDelete = head;
            prev->next = head->next;
            head = head->next;
            toDelete->next = NULL;
        }
        else {
            toDelete = NULL;
            prev = head;
            head = head->next;
        }
        if(toDelete != NULL)
            delete(toDelete);
    }

    return dummy->next;
}

int main() {
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(2);
    head->next->next->next = new listNode(3);
    head->next->next->next->next = new listNode(4);

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

Πρόγραμμα Java

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
};

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
        return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        listNode dummy = new listNode(-1) , prev = dummy , toDelete;
        dummy.next = head;

        while(head != null) {
            if(head.value == val) {
                prev.next = head.next;
            }
            else {
                prev = head;
            }
            head = head.next;
        }

        return dummy.next;
    }

    public static void main(String args[]) {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(2);
        head.next.next.next = new listNode(3);
        head.next.next.next.next = new listNode(4);

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

Ανάλυση πολυπλοκότητας Διαγραφή συνδεδεμένων στοιχείων λίστας Leetcode Solution

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

ΕΠΙ), καθώς επαναλαμβάνουμε ολόκληρη τη λίστα μία φορά. N = μήκος της λίστας

Βλέπε επίσης
Συγχώνευση ταξινομημένης σειράς Leetcode Solution

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

Ο (1), καθώς έχουμε μόνο σταθερό χώρο μνήμης.