Linked List ကို Element တွေကို Leetcode ဖြေရှင်းချက်ဖယ်ရှားပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Capital One Facebook က Google Microsoft က
ချိတ်ဆက်စာရင်း စင်ကြယ်သောသိုလှောင်

ပြProbleနာဖော်ပြချက်

ဒီပြproblemနာမှာငါတို့နဲ့ချိတ်ဆက်ထားတယ် စာရင်း ၎င်း၏ node များကိန်းတန်ဖိုးများရှိခြင်းနှင့်အတူ။ တန်ဖိုးတူတူညီသော list မှအချို့သော node များကိုဖျက်ပစ်ရန်လိုသည် val ။ ပြproblemနာကိုဖြေရှင်းရန်မလိုအပ်ပါ နေရာ ဒါပေမယ့်ကျနော်တို့တ ဦး တည်းထိုကဲ့သို့သောချဉ်းကပ်မှုဆွေးနွေးပါလိမ့်မယ်။

နမူနာ

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

Linked List ကို Element တွေကို Leetcode ဖြေရှင်းချက်ဖယ်ရှားပါ

ချဉ်းကပ်နည်း (Recursive)

ကျနော်တို့လိုအပ်တဲ့စာရင်း၏ ဦး ခေါင်းကိုပြန်သွားဖို့တူညီတဲ့ function ကို recursurs ခေါ်နိုင်ပါတယ်။ ပေးထားသောစာရင်းနောက်ဆက်နောက်ဆက်များပေါ်ရှိလုပ်ဆောင်မှုကိုအခြေအနေအချို့နှင့်ခေါ်ဆိုခြင်းဖြင့်၎င်းကိုကျွန်ုပ်တို့ရရှိသည်။ သို့သော်စာရင်းဗလာမရှိလျှင်အခြေအနေကိုကိုင်တွယ်ရန်လိုသည်။ အထူးအမှုတစ်ခုရှိတယ်။

စာရင်း၏ ဦး ခေါင်းတူညီသောတန်ဖိုးကိုရှိပါက Val (input), ထို့နောက်ကျွန်ုပ်တို့သည်၎င်း၏နောက် node ပေါ်ရှိ function ကိုပြန်ပို့ရန်လိုအပ်သည်။ (function stack ပြီးစီးသည်နှင့်အမျှ) စာရင်း၏ယခင် node များနှင့်တွဲဖက်မည့်လက်ရှိ node ကိုရှောင်ရှားရန်ဤအရာကိုပြုလုပ်သည်။

ဖယ်ရှား linked စာရင်း element တွေကို 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), ဘယ်မှာ N ကို = စာရင်းအရှည်။ အဆိုးရွားဆုံးသောအမှု၌ကျွန်ုပ်တို့သည်တစ်ခုချင်းစီကိုသာသွားရောက်ကြည့်ရှုသည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁)။ ကုဒ်အောက်ပါအတိုင်းအဖြစ် အမြီးပြန်သွား.

ချဉ်းကပ်မှု (ကြားမှာ)

မည်သည့် node ကိုမဆိုဖျက်ပစ်ရန်အတွက်၎င်းသည်ယခင် node ၏လိပ်စာရှိရမည်။ ဒါကထိန်းသိမ်းထားဖို့စိတ်ကူးတစ်ခုပေးသည် လွန်ခဲ့သော စာရင်းထဲရှိအမှတ်အသားများကိုကြိုးကိုင်ရန်ကျွန်ုပ်တို့အားကူညီလိမ့်မည်။ ယခုအရေးကြီးသောအချက်မှာ list အတွင်းရှိပထမဆုံး node သည်ယခင် node မရှိပါ။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်စာရင်း၏အစတွင် sentinel node တစ်ခုထည့်ရန်လိုအပ်သည်။ ယခုကျွန်ုပ်တို့သည် list ၏ပထမဆုံး node (sentinel node ဘေးရှိ node) ကိုဖြတ်သန်း။ အောက်ပါအခြေအနေနှစ်ခုနှင့်ရင်ဆိုင်ရလိမ့်မည်။

1. ) node-> တန်ဖိုးကို == Val: ဤကိစ္စတွင်ခုနှစ်, ငါတို့သတ်မှတ်ပါလိမ့်မယ် prev-> လာမယ့် = node-> လာမယ့်။ ၎င်းသည်လက်ရှိ node ၏ယခင် connection ကိုနောက်ဆက်သွယ်မှုနှင့်ချိတ်ဆက်ပြီးလက်ရှိ node ကို အသုံးပြု၍ ဖျက်ပစ်လိမ့်မည်။ ဖျက်ပစ် (currentNode)

2. ) မဟုတ်ရင်ကျနော်တို့ပဲထားကြ၏ prev = ဦး ခေါင်း လာမည့် node များအဘို့။

အဆုံးမှာ sentinel ၏နောက်တစ်နေ့လိုအပ်သောစာရင်းဖြစ်ပါတယ်။

ဖယ်ရှား linked စာရင်း element တွေကို 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

ဖယ်ရှား linked စာရင်း Element တွေကို Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

အချိန်ရှုပ်ထွေး

အို (N)စာရင်းတစ်ခုလုံးကိုတစ်ကြိမ်တည်းဖြတ်သန်းသည်နှင့်အမျှ။ N ကို = စာရင်းအရှည်

အာကာသရှုပ်ထွေးမှု 

အို (၁)ကျနော်တို့သာစဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသအဖြစ်။