إزالة عناصر القائمة المرتبطة Leetcode Solution  


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

المشكلة بيان  

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

مثال

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

إزالة عناصر القائمة المرتبطة Leetcode Solution  

نهج (تكراري)  

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

إذا كان رأس القائمة له قيمة تساوي 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;
}

برنامج جافا

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 = طول القائمة. نزور كل عنصر مرة واحدة فقط في أسوأ الحالات.

انظر أيضا
ملء الفيضان LeetCode

تعقيد الفضاء 

يا (1). كما يلي رمز العودية الذيل.

نهج (تكراري)  

لحذف أي عقدة ، نحتاج إلى الحصول على عنوان العقدة السابقة ، حتى نتمكن من تحويل النقطة السابقة إلى النقطة التالية. هذا يعطي فكرة للحفاظ على ملف سابق المؤشر الذي سيساعدنا في معالجة المؤشرات في القائمة. الآن ، النقطة المهمة هي أن العقدة الأولى في القائمة لا تحتوي على أي عقدة سابقة. لذلك ، نحتاج إلى إضافة عقدة خافرة في بداية القائمة. الآن ، يمكننا اجتياز العقدة الأولى في القائمة (العقدة المجاورة للعقدة الخافرة) وسنواجه الشرطين التاليين:

1.) node-> value == val: في هذه الحالة ، سنقوم بتعيين prev-> next = node-> 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;
}

برنامج جافا

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

تعقيد الوقت

على)، حيث نكرر القائمة بأكملها مرة واحدة. N = طول القائمة

انظر أيضا
دمج حل Leetcode المصفوفات المصنفة

تعقيد الفضاء 

يا (1)، لأننا فقط مساحة ذاكرة ثابتة.