הסר את פתרונות ה- Leetcode של רשימת קישורים


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג קפיטל אחד פייסבוק Google מיקרוסופט
רשימה מקושרת אחסון טהור

הצהרת בעיה

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

דוגמה

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 להשלמת מספרים

מורכבות זמן

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

מורכבות בחלל 

O (1). לפי הקוד הבא רקורסיבית זנב.

גישה (איטרטיבי)

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

1.) node-> value == val: במקרה זה, נקבע הקודם-> הבא = צומת-> הבא. זה יחבר את הקודם של הצומת הנוכחי עם הבא של הצומת הנוכחי, וימחק את הצומת הנוכחי באמצעות: מחק (currentNode)

2.) אחרת, פשוט הגדרנו הקודם = ראש לצמתים הקרובים.

בסוף, הזקיף הבא הוא הרשימה הנדרשת.

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

ניתוח מורכבות של הסרת אלמנטים של רשימה מקושרת

מורכבות זמן

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

מורכבות בחלל 

O (1), כפי שאנחנו רק שטח זיכרון קבוע.