力扣 [203、707、206]-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 [203、707、206]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

203. Remove Linked List Elements

题目链接

解题思路：

创建新链表：自己的

创建新的链表：

定义一个新的头指针，并且将该指针指向一个空节点。
再定义一个当前指针，负责指向新链表的尾节点。之所以要让当前指针始终指向尾节点，是为了下次方便增添新的元素加入队列。
再定义一个遍历指针，负责对于原链表的遍历和检验。其实这里可以直接利用已经定义好的原链表的头指针进行遍历！因为在该方法中该头指针失去了意义。返回的时候也不用返回该头指针，返回的是新链表的头指针的 Next，为什么是 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) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* cur = dummyHead;

        while (cur->next != nullptr)
        {
            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;
    }
};

在原有链表上进行元素删除：自己的

在原有的链表上进行元素的删除：

考虑头节点的 val 值是否等于目标值，若等于的话，那么就要删除头节点，将头节点的下一个节点作为头节点！使用 while 循环：因为开头部分可能存在多个连续的节点的val值均等于 val；所以要用while删除，直到找到第一个不等于 val 值的节点！

while (head != null && head->val == val) {
	LinkNode* tmp = head;
	head = tmp->next;
	delete tmp;
}

接下来就是非头节点部分了，针对的就是中间节点部分值为 val 的。那么试想一下当你遇到一个中间节点值为val后，你会怎么删除呢？
首先定义一个遍历指针cur 指向头节点，由于此时的头节点head，必然是不等于val的，那么我们就从下一个节点开始检查，检查的前提是下一个节点不为空！所以判断条件就是：当前cur节点不为空，并且当前节点的下一个节点也不为空的时候，才可以循环。为什么要判断当前节点是否为空呢？请联想我们删除一个节点的操作，比如，此时cur节点指向的下一个节点为空，那么删除它的操作是：使得cur节点的指针域指向的是cur节点的下一个节点的下一个节点，而对于cur节点的下一个节点的下一个节点，我们也不知道其是否存在，但是还是会将它指向这个节点，那么就会存在为空的可能性！

实现代码：

在原有链表上操作版本：

/**
 * 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){
            ListNode* tmp = head;
            head = tmp->next;
            delete tmp;
        }

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

遇见的问题：

无！

题目总结：

链表的删除操作：
当你要删除一个节点的时候，是必须需要知道当前删除的节点才能够进行删除操作的！不仅要知道，还要能够索引！
所以删除一个节点的方式有两种：

要么你定义两个间隔为一的前后指针，后指针负责往后遍历筛查每个元素的值是否满足删除的条件，当满足删除条件的时候，就可以让前指针进行删除操作。当删除完后，或者不满足删除条件的时候，需要继续往后遍历对吧，那么前后指针就必须同时往后走一步，筛查，判断，同步走。
另外一种删除操作就是：找到第一个不为val值的节点，然后定义一个cur节点，每次判断cur的下一个节点是否为要删除的节点，若是的话，则删除cur->next后再移动cur节点。若不是的话，再走到当前判断后的节点。

显然第二种删除方法更优秀！！！！！

707.设计链表

题目链接

解题思路：

模拟：自己的思路

就是道模拟题，多画图模拟就行了！
关键在于怎么根据给定的 index 找到对应的节点进行相应的操作。

实现代码：

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        //delete命令指示释放了tmp指针原本所指的那部分内存，
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        tmp=nullptr;
        _size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

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

题目总结：

关键在于如何根据 index 快速找到对应的节点！

206.反转链表

题目链接

解题思路：

递归：自己的

递归的出口：我们需要反转链表，所以说我们可以找到最后一个节点，然后从后往前依次改变节点的方向，所以出口是：当节点为空的时候，即终止递归。
递归的返回值：我们每次都是反转一条边，一条边连接两个节点。那么假如当我们反转了两个节点之间的边的 arrow 的指向后，我们就需要返回到上一级中，返回已经处理好的链表。那么不难得出我们可以将整个链表分为三部分，如下图所示：
那么一级递归应该做什么：就是反转呗。我们从后往前反转。递归到底部后，开始回溯，回溯一次，反转一次。但是反转的话需要哪些信息呢？需要当前节点和其反转的节点，所以说明我们反转的时候，只能是从倒数第二个节点开始反转，若是倒数第一个节点的话，无法反转，也潜在的规定了反转的规则：只能是当前节点和其下一个节点进行反转操作！
cur：表示的是反转之后的链表的头节点，即反转前的链表的尾节点，因为最后题目要求我们返回的是反转后的链表的头节点。

实现代码：

/**
 * 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) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* cur = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return cur;
    }
};

双指针：别人的

反转链表的本质是一条边，两个节点，改变两个节点之间的边的方向即可。
所以说我们只需要从左往右依次确定我们的两个节点即可！
每次确定后，就让我们的后面的节点的指针域指向前面节点即可！
比如当前节点 cur 指向头节点，然后一个前驱节点 pre ，初始的时候指向空，之后设置一个临时指针 tmp，cur 节点先跳转到下一个节点，然后 tmp 指向的节点，指向 pre 节点，然后pre节点指向tmp节点，

实现代码：

/**
 * 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* cur = head;
        ListNode* pre = nullptr;

        while (cur != nullptr) 
        {
            ListNode* tmp = cur;
            cur = cur->next;
            tmp->next = pre;
            pre = tmp;
        }
        return pre;
    }
};

双指针版本递归，即实质是替换了原有的 while 循环而已！

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};