總結(jié)概述

鏈表理論基礎(chǔ)

鏈表是一種通過(guò)指針串聯(lián)的線性結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)由兩部分組成，一個(gè)是數(shù)據(jù)域一個(gè)是指針域（存放指向下一個(gè)節(jié)點(diǎn)的指針），最后一個(gè)節(jié)點(diǎn)的指針域指向null（空指針的意思）。

鏈表的類型?

1、單鏈表?

單鏈表中的指針域只能指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。?

2、雙鏈表

雙鏈表：每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向下一個(gè)節(jié)點(diǎn)，一個(gè)指向上一個(gè)節(jié)點(diǎn)。

雙鏈表 既可以向前查詢也可以向后查詢。

3、循環(huán)鏈表

鏈表存儲(chǔ)方式

鏈表是通過(guò)指針域的指針鏈接在內(nèi)存中各個(gè)節(jié)點(diǎn)。

????????所以鏈表中的節(jié)點(diǎn)在內(nèi)存中不是連續(xù)分布的 ，而是散亂分布在內(nèi)存中的某地址上，分配機(jī)制取決于操作系統(tǒng)的內(nèi)存管理。

上圖鏈表起始節(jié)點(diǎn)為2， 終止節(jié)點(diǎn)為7， 各節(jié)點(diǎn)分布在內(nèi)存的不同地址空間上，通過(guò)指針串聯(lián)。

鏈表的定義

// 單鏈表
struct ListNode {
    int val;  // 節(jié)點(diǎn)上存儲(chǔ)的元素
    ListNode *next;  // 指向下一個(gè)節(jié)點(diǎn)的指針
    ListNode(int x) : val(x), next(NULL) {}  // 節(jié)點(diǎn)的構(gòu)造函數(shù)
};

鏈表的操作

1、刪除節(jié)點(diǎn)?

將C節(jié)點(diǎn)的next指針指向E節(jié)點(diǎn)就可以了。在C++里再手動(dòng)釋放這個(gè)D節(jié)點(diǎn)，釋放這塊內(nèi)存。

2、添加節(jié)點(diǎn)?

可以看出鏈表的增添和刪除都是O(1)操作，也不會(huì)影響到其他節(jié)點(diǎn)。

但是要注意，要是刪除第五個(gè)節(jié)點(diǎn)，需要從頭節(jié)點(diǎn)查找到第四個(gè)節(jié)點(diǎn)通過(guò)next指針進(jìn)行刪除操作，查找的時(shí)間復(fù)雜度是O(n)。

性能分析

數(shù)組在定義的時(shí)候，長(zhǎng)度就是固定的，如果想改動(dòng)數(shù)組的長(zhǎng)度，就需要重新定義一個(gè)新的數(shù)組。

鏈表的長(zhǎng)度可以不固定，并且可以動(dòng)態(tài)增刪， 適合數(shù)據(jù)量不固定，頻繁增刪，較少查詢的場(chǎng)景。

203. 移除鏈表元素

解題思路及代碼

鏈表操作的兩種方式：

• 直接使用原來(lái)的鏈表來(lái)進(jìn)行刪除操作。
• 設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)在進(jìn)行刪除操作。

第一種操作：

直接使用原來(lái)的鏈表來(lái)進(jìn)行移除

????????在單鏈表中移除頭結(jié)點(diǎn) 和 移除其他節(jié)點(diǎn)的操作方式是不一樣，其實(shí)在寫(xiě)代碼的時(shí)候也會(huì)發(fā)現(xiàn)，需要單獨(dú)寫(xiě)一段邏輯來(lái)處理移除頭結(jié)點(diǎn)的情況。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 刪除頭結(jié)點(diǎn)
        while (head != NULL && head->val == val) { // 注意這里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 刪除非頭結(jié)點(diǎn)
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

第二種操作：

可以設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)，以一種統(tǒng)一的邏輯來(lái)移除

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)
        dummyHead->next = head; // 將虛擬頭結(jié)點(diǎn)指向head，這樣方面后面做刪除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(1）

707. 設(shè)計(jì)鏈表

class MyLinkedList {
public:
    MyLinkedList() {
        this->size = 0;
        this->head = new ListNode(0);
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode *cur = head;
        for (int i = 0; i <= index; i++) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        index = max(0, index);
        size++;
        ListNode *pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        ListNode *toAdd = new ListNode(val);
        toAdd->next = pred->next;
        pred->next = toAdd;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        ListNode *pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        ListNode *p = pred->next;
        pred->next = pred->next->next;
        delete p;
    }
private:
    int size;
    ListNode *head;

};

206. 反轉(zhuǎn)鏈表

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-640736.html

ListNode* reverseList(ListNode* head) {
    ListNode *cur = head; // cur 指向當(dāng)前節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始
    ListNode *pre = NULL; // pre 指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，初始為空
    ListNode* temp; // 用于暫存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

    while (cur != NULL) { // 遍歷整個(gè)鏈表
        temp = cur->next; // 保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，防止斷鏈
        cur->next = pre; // 將當(dāng)前節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，完成翻轉(zhuǎn)操作

        // 更新 pre 和 cur 指針
        pre = cur;
        cur = temp;
    }
    return pre; // 返回翻轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)
}

到了這里，關(guān)于代碼隨想錄 - 鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！