حذف عناصر لیست پیوندی راه حل کد  


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ یکی از سرمایه فیس بوک گوگل مایکروسافت
الگوریتم برنامه نویسی مصاحبه مصاحبه آماده LeetCode LeetCodeSolutions لینک شده ذخیره سازی خالص

بیان مسأله  

در این مشکل ، پیوندی به ما داده می شود فهرست با گره های آن دارای مقادیر عدد صحیح است. ما باید برخی از گره ها را از لیست حذف کنیم که دارای ارزش برابر هستند وال مشکل نیازی به حل نیست درجا اما ما در مورد چنین رویکردی بحث خواهیم کرد.

مثال

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

حذف عناصر لیست پیوندی راه حل کدسنجاق  

رویکرد (بازگشتی)  

ما می توانیم برای بازگرداندن سر لیست مورد نیاز ، به صورت بازگشتی همان عملکرد را فراخوانی کنیم. ما با فراخوانی تابع در پسوندهای بعدی لیست داده شده با برخی شرایط به این مهم دست می یابیم. با این حال ، باید لیست اصلی را خالی کنیم. فقط یک مورد خاص وجود دارد:

اگر سر لیست مقداری برابر با داشته باشد val (ورودی) ، سپس ، باید عملکردی را که در گره بعدی آن فراخوانی شده است ، برگردانیم. این کار برای جلوگیری از گره فعلی اضافه شده به گره های قبلی لیست (با تکمیل پشته عملکرد) انجام می شود.

پیاده سازی حذف لینک پیوندی عناصر راه حل کد

برنامه 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

تجزیه و تحلیل پیچیدگی تعداد متغیر محلول کد کد

پیچیدگی زمان

بر)، جایی که N = طول لیست. ما در بدترین حالت فقط یکبار از هر عنصر بازدید می کنیم.

همچنین مشاهده کنید
سیل پر LeetCode

پیچیدگی فضا 

O (1). همانطور که کد به شرح زیر است بازگشت دم.

رویکرد (تکراری)  

برای حذف هر گره ، باید آدرس گره قبلی آن را داشته باشیم تا بتوانیم نکته قبلی را به گره بعدی آن برسانیم. این یک ایده برای حفظ a می دهد قبلی اشاره گر است که به ما کمک می کند تا اشاره گرها را در لیست دستکاری کنیم. حال ، نکته مهم این است که اولین گره در لیست هیچ گره قبلی ندارد. بنابراین ، ما باید یک گره نگهبان در ابتدای لیست اضافه کنیم. اکنون می توانیم از اولین گره در لیست عبور کنیم (گره کنار گره نگهبان) و با دو شرط زیر روبرو خواهیم شد:

1.) node-> value == val: در این حالت ، ما تنظیم خواهیم کرد prev-> next = node-> next. با این کار گره قبلی را به گره فعلی بعدی متصل می کنیم و گره فعلی را با استفاده از حذف می کنیم: حذف (currentNode)

2.) در غیر این صورت ، ما فقط تنظیم می کنیم prev = سر برای گره های آینده

در پایان ، نگهبان بعدی لیست مورد نیاز است.

پیاده سازی حذف لینک پیوندی عناصر راه حل کد

برنامه 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

تجزیه و تحلیل پیچیدگی حذف عناصر لیست پیوندی راه حل کد

پیچیدگی زمان

بر)، همانطور که یکبار کل لیست را تکرار می کنیم. N = طول لیست

همچنین مشاهده کنید
محلول آرایه های مرتب شده را ادغام کنید

پیچیدگی فضا 

O (1)، همانطور که فقط فضای حافظه ثابت داریم.

1