ลบองค์ประกอบรายการที่เชื่อมโยง Leetcode โซลูชัน


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก ทุนหนึ่ง Facebook Google ไมโครซอฟท์
รายการที่เชื่อมโยง Pure Storage

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับการเชื่อมโยง รายการ ด้วยโหนดที่มีค่าจำนวนเต็ม เราจำเป็นต้องลบบางโหนดออกจากรายการซึ่งมีค่าเท่ากับ Val ปัญหาไม่ต้องการให้แก้ไข ในสถานที่ แต่เราจะหารือเกี่ยวกับแนวทางดังกล่าว

ตัวอย่าง

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

ลบองค์ประกอบรายการที่เชื่อมโยง Leetcode โซลูชัน

แนวทาง (เรียกซ้ำ)

เราสามารถเรียกใช้ฟังก์ชันเดิมซ้ำเพื่อส่งคืนส่วนหัวของรายการที่ต้องการได้ เราบรรลุสิ่งนี้ได้โดยการเรียกใช้ฟังก์ชันในส่วนต่อท้ายของรายการที่กำหนดพร้อมเงื่อนไขบางประการ อย่างไรก็ตามเราจำเป็นต้องจัดการกรณีฐานเมื่อรายการว่างเปล่า มีกรณีพิเศษเพียงกรณีเดียว:

หากส่วนหัวของรายการมีค่าเท่ากับ 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 ส่วนเติมเต็ม

ความซับซ้อนของเวลา

บน)โดยที่ N = ความยาวของรายการ เราเยี่ยมชมแต่ละองค์ประกอบเพียงครั้งเดียวในกรณีที่เลวร้ายที่สุด

ความซับซ้อนของอวกาศ 

O (1). ดังรหัสดังนี้ การเรียกซ้ำหาง.

แนวทาง (ย้ำ)

ในการลบโหนดใด ๆ เราจำเป็นต้องมีที่อยู่ของโหนดก่อนหน้าเพื่อที่เราจะได้ทำให้จุดก่อนหน้าไปยังโหนดถัดไป สิ่งนี้ให้แนวคิดในการรักษาไฟล์ ก่อน ตัวชี้ที่จะช่วยเราจัดการตัวชี้ในรายการ ตอนนี้ประเด็นสำคัญคือโหนดแรกในรายการไม่มีโหนดก่อนหน้า ดังนั้นเราต้องเพิ่มโหนด sentinel ที่ด้านบนของรายการ ตอนนี้เราสามารถข้ามผ่านโหนดแรกในรายการ (โหนดถัดจากโหนด sentinel) และต้องเผชิญกับเงื่อนไขสองประการดังนี้:

1. ) node-> value == val: ในกรณีนี้เราจะตั้งค่า ก่อนหน้า -> ถัดไป = โหนด -> ถัดไป สิ่งนี้จะเชื่อมต่อก่อนหน้าของโหนดปัจจุบันกับถัดไปของโหนดปัจจุบันและลบโหนดปัจจุบันโดยใช้: ลบ (currentNode)

2. ) มิฉะนั้นเราจะตั้งค่า ก่อนหน้า = หัว สำหรับโหนดที่จะเกิดขึ้น

ในตอนท้ายรายการถัดไปของ Sentinel คือรายการที่ต้องการ

การดำเนินการลบองค์ประกอบรายการที่เชื่อมโยง 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 Solution

ความซับซ้อนของเวลา

บน)ในขณะที่เราทำซ้ำรายการทั้งหมดครั้งเดียว N = ความยาวของรายการ

ความซับซ้อนของอวกาศ 

O (1)เนื่องจากเรามีพื้นที่หน่วยความจำคงที่เท่านั้น