Байланыстырылған тізімнің элементтерін алып тастаңыз


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg Capital One Facebook Google Microsoft
Байланыстырылған тізім Таза сақтау

Проблемалық мәлімдеме

Бұл мәселеде бізге сілтеме берілген тізім оның түйіндері бүтін мәнге ие. Біз тізімнен мәні бар кейбір түйіндерді жоюымыз керек вал. Мәселе шешуді талап етпейді орында бірақ біз осындай тәсілдердің бірін талқылаймыз.

мысал

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

Байланыстырылған тізімнің элементтерін алып тастаңыз

Тәсіл (рекурсивті)

Қажетті тізімнің басын қайтару үшін біз бірдей функцияны рекурсивті түрде шақыра аламыз. Бұған біз берілген шарттың келесі жалғауларындағы функцияны кейбір шарттармен шақыру арқылы қол жеткіземіз. Алайда, тізім бос болған кезде біз негізгі істі қарауымыз керек. Тек бір ерекше жағдай бар:

Егер тізімнің басында мәні тең болса 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 шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (N), мұндағы N = тізімнің ұзындығы. Біз әр элементті ең нашар жағдайда бір рет қана аралаймыз.

Ғарыштың күрделілігі 

O (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;
}

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

Байланысты тізім элементтерін жоюдың күрделілігін талдау Leetcode шешімі

Уақыттың күрделілігі

O (N), өйткені біз бүкіл тізімді бір рет қайталаймыз. N = тізімнің ұзындығы

Ғарыштың күрделілігі 

O (1), біз тек тұрақты жады кеңістігі ретінде.