手把手教你完整實現一個鏈表

作者 | 梁唐

出品 | 公衆號：Coder 梁（ID：Coder_LT）

大家好，我是梁唐。

移除鏈表元素

給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，並返回 新的頭節點 。

分析

本題是鏈表應用的裸題，考察的是對鏈表刪除操作的掌握。我們很容易就寫出代碼：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* pt = head;
        
        // 使用while循環遍歷鏈表
        while (pt != nullptr && pt->next != nullptr) {
            if (pt->next->val == val) {
                pt->next = pt->next->next;
            // 注意這裏的else
            }else pt = pt->next;
        }
        return head;
    }
};

注意一點小細節，由於鏈表的刪除操作是pt->next = pt->next->next。即將當前的next指針指向再之後的一個元素，這就導致了我們每次判斷的都是下一個元素是否要刪除，而非當前元素。並且，在刪除了下一個元素之後，雖然當前指針沒有變化，但下一個元素已經變了，所以我們不需要移動指針了。

另外還有一個小問題：如果開頭就是要刪除的元素怎麼辦，我們沒有比head更早的節點了，又怎麼刪除head呢？如果試着提交一下上面的代碼，就會發現無法通過頭一個元素就需要刪除的 case。

針對這個問題，一種比較容易想到的方法是我們先對鏈表的頭部進行特判，先將頭部所有等於val的節點全部刪除，找到新的head指針之後，再執行上面的操作。

這當然是沒問題的，但解決這個問題，我們有更優雅的方法，並且這個方法的使用頻率非常高，幾乎在所有鏈表相關的問題中都可以使用。

這個方法就是創建一個虛擬的頭節點，這個頭節點是我們創建出來的，所以無論如何它都不會刪除。所以不知道返回的頭節點是什麼的問題也就不存在了。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* nd = new ListNode();
        nd->next = head;

        ListNode* pt = nd;
        
        while (pt != nullptr && pt->next != nullptr) {
            if (pt->next->val == val) {
                auto tmp = pt->next;
                pt->next = pt->next->next;
                delete tmp;
            }else pt = pt->next;
        }
        return nd->next;
    }
};

小試牛刀之後我們再來看一題：LeetCode 707 設計鏈表。

設計鏈表

設計鏈表的實現。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節點應該具有兩個屬性：val 和 next。val 是當前節點的值，next 是指向下一個節點的指針 / 引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點。假設鏈表中的所有節點都是 0-index 的。

在鏈表類中實現這些功能：

get(index)：獲取鏈表中第 index 個節點的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個元素之前添加一個值爲 val 的節點。插入後，新節點將成爲鏈表的第一個節點。
addAtTail(val)：將值爲 val 的節點追加到鏈表的最後一個元素。
addAtIndex(index,val)：在鏈表中的第 index 個節點之前添加值爲 val 的節點。如果 index 等於鏈表的長度，則該節點將附加到鏈表的末尾。如果 index 大於鏈表長度，則不會插入節點。如果index小於 0，則在頭部插入節點。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節點。

分析

在這道題當中我們要實現一個鏈表的類，提供題意當中列舉的這些方法。

LeetCode 當中這類的問題很多，平臺已經爲我們定義好了代碼框架，我們只需要實現細節。這是一個瞭解和學習面向對象非常好的機會，強烈建議初學乍練的萌新不要錯過。

class MyLinkedList {
public:
    MyLinkedList() {

    }
    
    int get(int index) {

    }
    
    void addAtHead(int val) {

    }
    
    void addAtTail(int val) {

    }
    
    void addAtIndex(int index, int val) {

    }
    
    void deleteAtIndex(int index) {

    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

首先聲明，這道題因爲涉及末尾插入元素以及指定下標添加、刪除元素，涉及的細節更多，要比看起來的更困難一些。

觀察代碼可以發現只是替我們定義好了鏈表的類，沒有鏈表中節點的相關定義，首先寫好這個部分：

class MyLinkedList {
public:
    struct Node {
        int val;
        Node* next;
        Node(int x, Node* pt=nullptr): val(x), next(pt) {}
    };
...

題目中需要我們往末尾插入元素的操作，因此我們除了需要head之外，還需要一個tail記錄最後一個元素。head是虛擬頭節點，永遠不變，而tail是尾節點，指向最後一個節點的位置。因此隨着我們的操作，tail可能會發生變化。這一點非常重要，切記。

初始化時我們令tail = head，這樣才能保證不論我們往頭部還是尾部插入元素得到的結果相同。

Node *head, *tail;

MyLinkedList() {
    head = new Node(0);
    tail = head;
}

我非常推薦在開始編碼之前先實現一個printAll函數，用來打印鏈表當中的所有元素。這樣會比較方便我們debug。

void printAll() {
    auto pt = head;
    while (pt->next != nullptr) {
        cout << pt->next->val << endl;
        pt = pt->next;
    }
}

之後從易到難，我們先來實現最簡單的從頭部插入元素以及從末尾插入元素。

void addAtHead(int val) {
    head->next = new Node(val, head->next);
    // 注意移動tail
    if (head == tail) tail = head->next;
}

void addAtTail(int val) {
    tail->next = new Node(val, nullptr);
    // 移動tail
    tail = tail->next;
}

addAtTail很簡單，我們在tail指針後面創建一個新的節點即可，但別忘了創建好了之後當前的tail就不是最後一個節點的位置了，要更新一下。

同樣在addAtHead函數當中也有這個問題，剛開始的時候鏈表爲空，往head後面添加元素就相當於往末尾添加。因此要加上特判，當head等於tail時，也要更新tail。

接下來比較好實現的是get函數，需要返回指定下標的元素。我們只需要使用for循環從head開始移動index+1次，如果沒到鏈表結尾的話，返回指向的元素即可。

int get(int index) {
    auto pt = head;
    for (int i = 0; i <= index; i++) {
        pt = pt->next;
        if (pt == nullptr) return -1;
    }
    return pt->val;
}

get沒問題了之後，稍微修改一下就是addAtIndex函數。這裏要小心，由於我們在插入元素的時候都會修改插入之前的節點，所以這裏我們只需要移動index次，比上面要少一次。

void addAtIndex(int index, int val) {
    auto pt = head;
    for (int i = 0; i < index; i++) {
        pt = pt->next;
        if (pt == nullptr) return ;
    }
    pt->next = new Node(val, pt->next);
    if (pt == tail) tail = pt->next;
}

最後纔是刪除元素，基本上是插入元素的逆操作。除了小心空指針之外，還要注意如果刪除的節點剛好是tail，要把tail往前移。

void deleteAtIndex(int index) {
    auto pt = head;
    for (int i = 0; i < index; i++) {
        pt = pt->next;
        if (pt == nullptr) return ;
    }
    auto tmp = pt->next;
    if (tmp == nullptr) return ;
    pt->next = pt->next->next;
    if (tmp == tail) tail = pt;
    delete tmp;
}

最後貼一下完整代碼：

class MyLinkedList {
public:
    struct Node {
        int val;
        Node* next;
        Node(int x, Node* pt=nullptr): val(x), next(pt) {}
    };

    Node *head, *tail;

    MyLinkedList() {
        head = new Node(0);
        tail = head;
    }
    
    int get(int index) {
        auto pt = head;
        for (int i = 0; i <= index; i++) {
            pt = pt->next;
            if (pt == nullptr) return -1;
        }
        return pt->val;
    }
    
    void addAtHead(int val) {
        head->next = new Node(val, head->next);
        if (head == tail) tail = head->next;
    }
    
    void addAtTail(int val) {
        tail->next = new Node(val, nullptr);
        tail = tail->next;
    }
    
    void addAtIndex(int index, int val) {
        auto pt = head;
        for (int i = 0; i < index; i++) {
            pt = pt->next;
            if (pt == nullptr) return ;
        }
        pt->next = new Node(val, pt->next);
        if (pt == tail) tail = pt->next;
    }
    
    void deleteAtIndex(int index) {
        auto pt = head;
        for (int i = 0; i < index; i++) {
            pt = pt->next;
            if (pt == nullptr) return ;
        }
        auto tmp = pt->next;
        if (tmp == nullptr) return ;
        pt->next = pt->next->next;
        if (tmp == tail) tail = pt;
        delete tmp;
    }
};

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/kS_zJyceqzBfT3Vww32zMA

移除鏈表元素

分析

設計鏈表

分析

猜你喜歡