연결된 목록 요소 Leetcode 솔루션 제거


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 자본 하나 페이스북 서비스 구글 Microsoft
연결된 목록 순수 저장

문제 정책

이 문제에서 우리는 링크 된 명부 노드에 정수 값이 있습니다. 목록에서 다음과 같은 값을 가진 일부 노드를 삭제해야합니다. 발. 문제를 해결할 필요가 없습니다. 그 자리에서 그러나 우리는 그러한 접근법에 대해 논의 할 것입니다.

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

자바 프로그램

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). 코드는 다음과 같습니다. 꼬리 재귀.

접근 방식 (반복)

노드를 삭제하려면 이전 노드의 주소가 있어야 이전 지점을 다음 노드로 만들 수 있습니다. 이것은 유지하는 아이디어를 제공합니다 너무 이른 목록에서 포인터를 조작하는 데 도움이되는 포인터. 이제 중요한 점은 목록의 첫 번째 노드에 이전 노드가 없다는 것입니다. 따라서 목록 시작 부분에 센티넬 노드를 추가해야합니다. 이제 목록의 첫 번째 노드 (감시 노드 옆의 노드)를 통과 할 수 있으며 다음 두 가지 조건에 직면하게됩니다.

1.) node-> value == val :이 경우 우리는 이전-> 다음 = 노드-> 다음. 이것은 현재 노드의 이전 노드와 현재 노드의 다음 노드를 연결하고 다음을 사용하여 현재 노드를 삭제합니다. 삭제 (currentNode)

2.) 그렇지 않으면 우리는 이전 = 머리 다가오는 노드를 위해.

마지막에 센티넬의 다음 항목이 필수 목록입니다.

링크 된 목록 요소 제거 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;
}

자바 프로그램

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 솔루션의 복잡성 분석

시간 복잡성

의 위에), 전체 목록을 한 번 반복합니다. N = 목록 길이

공간 복잡성 

O (1), 우리는 일정한 메모리 공간 만 사용합니다.