සම්බන්ධිත ලැයිස්තු මූලද්‍රව්‍ය ලීට්කෝඩ් විසඳුම ඉවත් කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ප්රාග්ධන එක් ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට්
සම්බන්ධිත ලැයිස්තුව පිරිසිදු ගබඩා කිරීම

ගැටළු ප්රකාශය

මෙම ගැටළුව තුළ, අපට සම්බන්ධිතයක් ලබා දී ඇත ලැයිස්තුව එහි නෝඩ් සමඟ පූර්ණ සංඛ්‍යා අගයන් ඇත. සමාන වටිනාකමක් ඇති ලැයිස්තුවෙන් සමහර නෝඩ් මකා දැමිය යුතුය වැල් ගැටළුව විසඳීම අවශ්ය නොවේ ස්ථානයේ නමුත් අපි එවැනි එක් ප්‍රවේශයක් ගැන සාකච්ඡා කරමු.

උදාහරණයක්

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

සම්බන්ධිත ලැයිස්තු මූලද්‍රව්‍ය ලීට්කෝඩ් විසඳුම ඉවත් කරන්න

ප්‍රවේශය (පුනරාවර්තන)

අවශ්‍ය ලැයිස්තුවේ ප්‍රධානියා ආපසු ලබා දීම සඳහා අපට එකම ශ්‍රිතය පුනරාවර්තනය කළ හැකිය. අපි මෙය සාක්ෂාත් කරගන්නේ යම් කොන්දේසි සහිතව ලබා දී ඇති ලැයිස්තුවේ පසු උපසර්ග මත ශ්‍රිතය ඇමතීමෙන් ය. කෙසේ වෙතත්, ලැයිස්තුව හිස් වූ විට අපි මූලික නඩුව හැසිරවිය යුතුය. ඇත්තේ එක් විශේෂ අවස්ථාවක් පමණි:

ලැයිස්තුවේ ශීර්ෂයට සමාන අගයක් තිබේ නම් අගය (ආදානය), ඉන්පසුව, අපි එහි ඊළඟ නෝඩයට කැඳවූ ශ්‍රිතය නැවත ලබා දිය යුතුය. මෙය සිදු කරනුයේ වත්මන් නෝඩය ලැයිස්තුවේ පෙර නෝඩ් වලට එකතු කිරීම වළක්වා ගැනීම සඳහා ය (ශ්‍රිත තොගය අවසන් වූ විට).

ඉවත් කළ සම්බන්ධිත ලැයිස්තු මූලද්‍රව්‍ය ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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 = ලැයිස්තුවේ දිග. අපි එක් එක් මූලද්රව්ය වෙත පිවිසෙන්නේ නරකම අවස්ථාවක එක් වරක් පමණි.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1). කේතය පහත පරිදි වලිග පුනරාවර්තනය.

ප්රවේශය (අනුක්රමික)

ඕනෑම නෝඩයක් මකාදැමීම සඳහා, අපට එහි පෙර නෝඩයේ ලිපිනය තිබිය යුතුය, එවිට අපට පෙර කරුණ එහි ඊළඟ දෙසට යොමු කළ හැකිය. මෙය නඩත්තු කිරීමට අදහසක් ලබා දෙයි කලින් ලැයිස්තුවේ දර්ශකයන් හැසිරවීමට අපට උපකාරී වන දර්ශකය. දැන්, වැදගත් කරුණ නම් ලැයිස්තුවේ පළමු නෝඩයට පෙර නෝඩයක් නොමැති වීමයි. එබැවින්, අපි ලැයිස්තුවේ ආරම්භයේ දී සෙන්ඩිනල් නෝඩයක් එක් කළ යුතුය. දැන්, අපට ලැයිස්තුවේ පළමු නෝඩය හරහා ගමන් කළ හැකිය (සෙන්ඩිනල් නෝඩ් අසල ඇති නෝඩ්) පහත සඳහන් කොන්දේසි දෙකකට මුහුණ දෙනු ඇත:

1.) node-> value == val: මෙම අවස්ථාවේදී, අපි සකසමු prev-> next = node-> next. මෙය වත්මන් නෝඩයේ පෙර වත්මන් නෝඩය සමඟ සම්බන්ධ වන අතර වත්මන් නෝඩය මකා දමන්නේ: මකන්න (currentNode)

2.) එසේ නොමැති නම්, අපි දැන් සකස් කරමු prev = හිස ඉදිරියට එන නෝඩ් සඳහා.

අවසානයේදී, සෙන්ඩිනල් හි ඊළඟට අවශ්‍ය ලැයිස්තුව වේ.

ඉවත් කළ සම්බන්ධිත ලැයිස්තු මූලද්‍රව්‍ය ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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 = ලැයිස්තුවේ දිග

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1), අපි නිරන්තර මතක අවකාශයක් පමණක් බැවින්.