ດຶງອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg Capital One ເຟສບຸກ ກູໂກ Microsoft
ບັນຊີທີ່ເຊື່ອມໂຍງ Pure Storage

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບການເຊື່ອມໂຍງ ບັນຊີລາຍຊື່ ກັບຂໍ້ຂອງມັນມີຄຸນຄ່າເທົ່າກັບ. ພວກເຮົາຕ້ອງການລຶບບາງຂໍ້ອອກຈາກລາຍຊື່ທີ່ມີຄ່າເທົ່າກັບ val. ບັນຫາບໍ່ ຈຳ ເປັນຕ້ອງໄດ້ຮັບການແກ້ໄຂ ໃນ​ສະ​ຖານ​ທີ່ ແຕ່ພວກເຮົາຈະປຶກສາຫາລືກ່ຽວກັບວິທີການດັ່ງກ່າວ.

ຍົກຕົວຢ່າງ

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

ດຶງອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution

ວິທີການ (Recursive)

ພວກເຮົາສາມາດໂທຫາຟັງຊັນດຽວກັນກັບຄືນມາເພື່ອຕອບແທນບັນຊີລາຍຊື່ທີ່ຕ້ອງການ. ພວກເຮົາບັນລຸເປົ້າ ໝາຍ ນີ້ໂດຍການໂທຫາ ໜ້າ ທີ່ໃນບັນດາຜົນຕໍ່ມາຂອງບັນຊີລາຍຊື່ທີ່ມີໃນບາງເງື່ອນໄຂ. ເຖິງຢ່າງໃດກໍ່ຕາມ, ພວກເຮົາຕ້ອງຈັດການກັບກໍລະນີພື້ນຖານເມື່ອບັນຊີລາຍຊື່ບໍ່ຢູ່. ມີພຽງແຕ່ກໍລະນີພິເສດ ໜຶ່ງ ເທົ່ານັ້ນ:

ຖ້າຫົວ ໜ້າ ບັນຊີມີຄ່າເທົ່າກັບ val (ວັດສະດຸປ້ອນ), ຫຼັງຈາກນັ້ນ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງສົ່ງຄືນ ໜ້າ ທີ່ທີ່ເອີ້ນວ່າ node ຕໍ່ໄປ. ນີ້ແມ່ນເຮັດເພື່ອຫຼີກເວັ້ນການ node ໃນປະຈຸບັນທີ່ຈະຖືກສະແດງຢູ່ໃນຂໍ້ທີ່ຜ່ານມາຂອງບັນຊີລາຍຊື່ (ຍ້ອນວ່າ stack ຂອງຫນ້າທີ່ຖືກເຮັດແລ້ວ).

ການຈັດຕັ້ງປະຕິບັດໃນການ ກຳ ຈັດອົງປະກອບລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution

ໂຄງການ 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 Program

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 Solution

ຄວາມສັບສົນເວລາ

ໂອ (N), ບ່ອນທີ່ N = ຄວາມຍາວຂອງບັນຊີ. ພວກເຮົາໄປຢ້ຽມຢາມແຕ່ລະອົງປະກອບພຽງແຕ່ຄັ້ງດຽວໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1). ຕາມລະຫັດດັ່ງຕໍ່ໄປນີ້ ການຮຽກຄືນຫາງ.

ວິທີການ (ຄິດໄລ່)

ເພື່ອລົບລ້າງ node ໃດກໍ່ຕາມ, ພວກເຮົາຕ້ອງມີທີ່ຢູ່ຂອງ node ຂອງມັນກ່ອນ, ເພື່ອໃຫ້ພວກເຮົາສາມາດເຮັດໃຫ້ຈຸດທີ່ຜ່ານມາຊີ້ໃຫ້ເຫັນຕໍ່ໄປ. ນີ້ໃຫ້ຄວາມຄິດທີ່ຈະຮັກສາ ທີ່ຜ່ານມາ ຕົວຊີ້ຊຶ່ງຈະຊ່ວຍໃຫ້ພວກເຮົາສາມາດ ໝູນ ໃຊ້ຜູ້ຊີ້ ນຳ ໃນບັນຊີ. ໃນປັດຈຸບັນ, ຈຸດ ສຳ ຄັນແມ່ນວ່າ Node ທຳ ອິດໃນບັນຊີລາຍຊື່ບໍ່ມີ node ກ່ອນ ໜ້າ ນີ້. ດັ່ງນັ້ນ, ພວກເຮົາຕ້ອງການເພີ່ມ node ທີ່ຢູ່ໃນເບື້ອງຕົ້ນຂອງບັນຊີ. ດຽວນີ້, ພວກເຮົາສາມາດຂ້າມຜ່ານຂໍ້ ທຳ ອິດໃນບັນຊີ (node ​​ຕໍ່ node sentinel) ແລະຈະປະເຊີນກັບສອງເງື່ອນໄຂດັ່ງນີ້:

1. ) node-> ມູນຄ່າ == val: ໃນກໍລະນີນີ້, ພວກເຮົາຈະ ກຳ ນົດ prev-> ຕໍ່ໄປ = ຂໍ້ -> ຕໍ່ໄປ. ນີ້ຈະເຊື່ອມຕໍ່ node ກ່ອນ ໜ້າ ນີ້ກັບ node ຕໍ່ໄປ, ແລະລຶບ node ປັດຈຸບັນໂດຍໃຊ້: ລົບ (ປັດຈຸບັນ)

2. ) ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາພຽງແຕ່ຕັ້ງ prev = ຫົວ ສຳ ລັບຂໍ້ທີ່ ກຳ ລັງຈະມາເຖິງ.

ໃນຕອນທ້າຍ, ຕໍ່ໄປຂອງ sentinel ແມ່ນບັນຊີລາຍຊື່ທີ່ຕ້ອງການ.

ການຈັດຕັ້ງປະຕິບັດໃນການ ກຳ ຈັດອົງປະກອບລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution

ໂຄງການ 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 Program

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 Solution

ຄວາມສັບສົນເວລາ

ໂອ (N), ດັ່ງທີ່ພວກເຮົາຂຽນບັນຊີທັງ ໝົດ ຄັ້ງດຽວ. N = ຄວາມຍາວຂອງລາຍການ

ຄວາມສັບສົນໃນອະວະກາດ 

O (1), ດັ່ງທີ່ພວກເຮົາພຽງແຕ່ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່ເທົ່ານັ້ນ.