203. 移除鏈表元素

/**
 * 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) 
    {
       
        while (head != nullptr && head->val == val)
        {
            head = head->next;
        }
        ListNode* node = head;
        
        while (node != nullptr && node->next != nullptr)
        {
            if (node->next->val == val)
            {
                node->next = node->next->next;
            }
            else 
            {
                node = node->next;
            }
        }
        return head;
    }
};

707. 設(shè)計鏈表

class MyLinkedList {
public:
    struct linknode 
    {
        int val;
        linknode* next;
        linknode(int x): val(x), next(NULL){}
    };


    MyLinkedList() 
    {
        this->head = new linknode(0);
        this->size = 0;
    }
    
    int get(int index) 
    {
        linknode* cur = this->head;
        if (this->size == 0) return -1;
        else if (index > this->size-1) return -1;
        else 
        {
            for (int i=0; i<index; i++)
            {
                cur = cur->next;
            }
        }
        return cur->val;
    }
    
    void addAtHead(int val) 
    {
        if (this->size == 0)
        {
            this->head->val = val;
            this->size = 1;
        }
        else
        {
            linknode* cur = new linknode(val);
            linknode* tmp = this->head;
            this->head = cur;
            cur->next = tmp;
            this->size += 1; 
        }
    }
    
    void addAtTail(int val) 
    {
        if (this->size == 0)
        {
            this->head->val = val;
            this->size = 1;
        }
        else
        {
            linknode* cur = new linknode(val);
            linknode* tmp = this->head;
            while (tmp->next != NULL)
            {
                tmp = tmp->next;
            }
            tmp->next = cur;
            this->size++;
        }



    }
    
    void addAtIndex(int index, int val) 
    {
        if (index > this->size) return;
        else if (index == this->size) addAtTail(val);
        else if (index == 0) addAtHead(val);
        else
        {
            linknode* cur = this->head;
            linknode* newnode = new linknode(val);
            for (int i=0; i<index-1; i++)
            {
                cur = cur->next;
            }
            linknode* tmp = cur->next;
            cur->next = newnode;
            newnode->next = tmp;
            this->size++;
        }


    }
    
    void deleteAtIndex(int index) 
    {
        if (this->size == 0) return;
        else if (index > this->size-1) return;
        else{
            if (index == 0) this->head = this->head->next;
            else if (index == this->size-1) 
            {
                linknode* cur = this->head;
                while (cur != NULL && cur->next != NULL && cur->next->next != NULL)
                {
                    cur = cur->next;
                }
                cur->next = NULL;
            }
            else
            {
                linknode* cur = this->head;
                for (int i=0; i<index-1; i++)
                {
                    cur = cur->next;
                }
                cur->next = cur->next->next;
            }
            this->size--;
        }

    }

private:
    linknode *head;
    int size;

};

/**
 * 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);
 */

206. 反轉(zhuǎn)鏈表

??????? 自己寫的是從后往前去反轉(zhuǎn)，沒想到可以從前往后反轉(zhuǎn)的方法，以為地址不連續(xù)并且無法根據(jù)索引找地址就沒辦法做，看了雙指針方法后才發(fā)現(xiàn)如何從前往后反轉(zhuǎn)，其實只要記錄每個結(jié)點的地址就可以了，還是對鏈表的概念把握的不好，需要多刷題。

自己做的：

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (head==nullptr) return head;
        if (head->next==nullptr) return head;
        ListNode* newnode = head;
        ListNode* tmp1 = head;
        // while (newnode != nullptr && newnode->next != nullptr && newnode->next->next != nullptr)
        // {
        //     newnode = newnode->next;
        // }
        // ListNode*
        int flag = 0;

        while (head->next != nullptr)
        {
            ListNode* cur = head;
            while (cur != nullptr && cur->next != nullptr && cur->next->next != nullptr)
            {
                cur = cur->next;
            }
            if (flag == 0)
            {
                newnode = cur->next;
                tmp1 = cur->next;
                cur->next = nullptr;
            }
            else
            {
                ListNode* tmp = cur->next;
                cur->next = nullptr;
                tmp1->next = tmp;
                tmp1 = tmp;
            }
            flag++;
        }
        tmp1->next = head;
        return newnode;

    }
};

雙指針：文章來源地址http://www.zghlxwxcb.cn/news/detail-826335.html

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一個節(jié)點
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一個節(jié)點，因為接下來要改變cur->next
            cur->next = pre; // 翻轉(zhuǎn)操作
            // 更新pre 和 cur指針
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

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