刪除鏈接列表元素Leetcode解決方案  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 第一資本 Facebook 谷歌 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;
}

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 =列表的長度。 在最壞的情況下,我們僅對每個元素進行一次訪問。

也可以看看
洪水填充LeetCode

空間複雜度 

O(1)。 如代碼所示 尾遞歸.

方法(迭代)  

為了刪除任何節點,我們需要擁有其前一個節點的地址,以便我們可以將前一個節點指向其下一個節點。 這給出了保持 指針,這將有助於我們操縱列表中的指針。 現在,重要的一點是列表中的第一個節點沒有任何先前的節點。 因此,我們需要在列表的開頭添加一個哨兵節點。 現在,我們可以遍歷列表中的第一個節點(前哨節點旁邊的節點),並將面臨以下兩個條件:

1.)node-> value == val:在這種情況下,我們將設置 prev-> next =節點-> next。 這會將當前節點的前一個節點與當前節點的下一個節點連接起來,並使用以下命令刪除當前節點: 刪除(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;
}

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解決方案的複雜性分析

時間複雜度

上),因為我們一次遍歷整個列表。 N =清單長度

也可以看看
合併排序數組Leetcode解決方案

空間複雜度 

O(1),因為我們只有恆定的內存空間。

1