203-移除鏈表元素

題目鏈接：移除鏈表元素

思路：鏈表中元素的添加和刪除關(guān)鍵是要保證不斷鏈且指向關(guān)系正確。對于刪除操作，鏈的修改涉及將待刪除元素的前一個元素指向待刪除元素的后一個元素，因此在判斷當前元素是否需要刪除時，要記錄當前元素的前后指針。

1.刪除頭結(jié)點時另作考慮

算法描述：根據(jù)上述描述，刪除操作需要記錄當前結(jié)點的前一個指針，而對于頭結(jié)點而言沒有前一個指針，因此對于將頭結(jié)點單獨考慮。對于后續(xù)結(jié)點，首先記錄前一個結(jié)點再判斷當前結(jié)點是否需要刪除，若刪除則將前一個結(jié)點指向當前結(jié)點的next。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //刪除頭結(jié)點時另做考慮
        while(head != nullptr && head->val == val){
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }
        
        ListNode *prev = head;
        while(prev != nullptr && prev->next != nullptr){
            ListNode *cur = prev->next;
            if(cur->val == val){
                prev->next = prev->next->next;
                delete cur;
            }
            else
                prev = cur;
        }
        return head;
    }
};

易錯：代碼中通過prev來進入循環(huán)，若當前結(jié)點需要刪除，刪除后對于下一個需要處理的結(jié)點的前一個結(jié)點prev仍然時當前這個，不需要進行修改。若結(jié)點不需要刪除，才需要將prev向后移。

2.添加一個虛擬頭結(jié)點

算法描述：添加一個虛擬的頭結(jié)點，從而使得若需要刪除頭結(jié)點時不需要另作考慮。運算完成后返回創(chuàng)建的虛擬結(jié)點的next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 添加一個虛擬頭結(jié)點
        ListNode *hnode = new ListNode(0);
        hnode->next = head;

        ListNode *prev = hnode;
        while(prev != nullptr && prev->next != nullptr){
            ListNode *cur = prev->next;
            if(cur->val == val){
                prev->next = prev->next->next;
                delete cur;
            }
            else
                prev = cur;
        }
        head = hnode->next;
        delete hnode;
        return head;
    }
};

注意：在創(chuàng)建虛擬結(jié)點后需要分配內(nèi)存空間（第15行）

707-設(shè)計鏈表

鏈表操作的基礎(chǔ)題，注意實現(xiàn)細節(jié)。不作詳細說明，參考官方題解or代碼隨想錄707.設(shè)計鏈表

206-反轉(zhuǎn)鏈表

題目鏈接：反轉(zhuǎn)鏈表

思路：暴力求解，定義一個新鏈表。但空間開銷大。 --> 查看題解：代碼隨想錄-反轉(zhuǎn)鏈表

算法描述：雙指針法，后指針確?？梢园凑赵湵淼捻樞虮闅v下去，前指針負責修改指向關(guān)系。

? ? ? ? --> 三個指針記錄 1）記錄當前要修改的指針cur? 2）記錄指向原鏈表中的next結(jié)點的指針b_next 3）記錄當前指針反轉(zhuǎn)之后指向的結(jié)點pre

? ? ? ? --> 指針開始遍歷，在開始前pre為nullptr。遍歷時，首先用b_next記錄當前指針的next，記錄后，修改當前的cur指向為pre。更新pre和cur，繼續(xù)遍歷鏈表。文章來源地址http://www.zghlxwxcb.cn/news/detail-596213.html

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *b_next;
        ListNode *cur = head;
        ListNode *pre = nullptr;
        
        while(cur){
            b_next = cur->next; // 保存原鏈表中當前結(jié)點的下一個結(jié)點
            cur->next = pre; // 翻轉(zhuǎn)

            pre = cur;
            cur = b_next;
        }

        return pre;

    }
};

到了這里，關(guān)于代碼隨想錄Day3 | 鏈表01-leetcode203、707、206的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！