代码随想录算法训练营第三天|203.移除链表元素、707.设计链表、206.反转链表

友友们，通过前两天的练习和坚持，我们数组部分的算法题已经学完了，不知道大家理解得怎么样，可以多做题多思考，题目做不出来不要死磕看看题解学习一下别人的思路哦！ 

移除链表元素：

203. 移除链表元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-linked-list-elements/submissions/477690164/题目思路：做链表这部分题目的一个前提就是大家要先掌握链表的知识，知道链表是怎样存储数据的。在移除链表元素这道题中我们要考虑头节点是否与要移除的元素相等，若相等就要移除头节点，那么就要更新头节点，还有一种方法是设置一个虚拟头节点。

• 原链表删除元素：在本题中首先我们要判断头节点 head 指向的元素是否需要删除，若需要就将头节点删除将头节点 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* temp ;
       while(head != NULL && head->val == val){
          temp = head;
          head = head->next;//链表中的第一个元素作为头指针，如果头指针指向元素与目标值相等就将头指针指向元素删除并将next元素作为头指针
          delete temp;
       }//用while是因为不一定有几个与val相同的值,要确保所有与目标值相等的元素都删除
       //如果头指针指向元素与目标值不相等，就定义一个指针指向头节点
        ListNode* cur = head;
       while(cur != NULL && cur->next != NULL){
         if(cur->next->val == val){
         temp = cur->next;
         cur->next = cur->next->next;//将与目标值相等的元素删除，并将下一个元素的地址放入前一个元素的next域
         delete temp;
       }else{
        cur = cur->next;//将指针向后移动
       } 
    }
    return head;
    }  
};

•  虚拟头节点方法：定义一个虚拟头节点，将虚拟头节点的 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;//为什么从指向dummyhead->next开始，是因为如果从指向它开始的话，相当于从指向头节点开始，如果要删除头结点的话还是要单独操作，就会增加时间复杂度。
      while(cur->next != NULL){
        if(cur->next->val == val){
           ListNode* temp = cur->next;
           cur->next = cur->next->next;
           delete temp;
        }else{
          cur = cur->next;
        }
      }
      return dummyhead->next;
    }  
};

---

设计链表 ：

707. 设计链表 - 力扣（LeetCode）https://leetcode.cn/problems/design-linked-list/description/题目思路：

 本题依然是用虚拟头结点的方法，结合C语言数据结构中的链表的各种操作，我们看一下具体代码。

class MyLinkedList {
public:
    struct LinkedNode {//定义链表节点结构体
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
    };
    //初始化链表
    MyLinkedList() {//链表属性的定义在下方
       dummyhead  = new LinkedNode(0);//定义一个虚拟头节点
       size = 0;//链表长度
    }
    int get(int index) {
        if(index > (size - 1) || index < 0){//如果下标不合法就返回-1
            return -1;
        }
        LinkedNode* cur = dummyhead->next;//cur指针从头节点开始移动
        while(index--){//不能是--index，因为如果index为0，指的是链表头节点，先自减再进入循环的话就少一个节点
            cur = cur->next;//如果index等于0，也就是只有一个节点，那么循环结束后cur指向的是那个唯一的节点,如果cur从虚拟头节点开始遍历，最后cur指向的是目标元素的前一个
        }
        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++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size||index < 0) return;
        LinkedNode* newnode = new LinkedNode(val);
        LinkedNode* cur = dummyhead;
        while(index--){//遍历链表直到下表为index的元素为止
            cur = cur->next;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= size||index < 0) return;
        LinkedNode* cur = dummyhead;
        while(index--){
            cur = cur->next;
        }
        LinkedNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = 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);
 */

---

反转链表 ：

206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/description/解题思路 ：

• 双指针法：定义两个指针，一个pre指向空，一个cur指向头节点，只要cur不指向空，就将箭头翻转，但是在这之前，要将cur->next保存下来否则就找不到了，在移动指针的时候要先将pre指向cur，再将cur指向cur->next（也就是临时存放cur->next的指针），移动到最后就是cur指向空，pre指向链表反转后的头节点，最后返回pre即可。

具体代码如下：

/**
 * 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* pre = NULL;
        ListNode* cur = head;
        ListNode* temp;
        while(cur != NULL){
            temp = cur->next;
            cur->next = pre;//反转链表
            pre = cur;//一定要先将pre指向cur，再将cur指向下一个，否则就找不到cur了
            cur = temp;
        }
        return pre;
    }
};

• 递归法： 递归的方法其实就是对双指针法的一个简化，思路一模一样。

/**
 * 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) {
       return reverse(head,NULL);//传入初始实参，初始化时cur指向头节点，pre指向空
    }
    ListNode* reverse(ListNode* cur,ListNode* pre){
        if(cur == NULL){
            return pre;
        }
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(temp,cur);//pre指向cur，cur指向temp
    }
};

心得：今天学的是链表这部分，因为我的数据结构还没学完，而且学的还是C语言版的，所以导致今天学的有些吃力，C++中的一些语法盲区还导致了编译错误，改bug浪费了好多时间 ，心态快崩了，接下来我要做的是去补一下C++的语法，还有vs的调试怎么调，以后有时间的话还是要实现以下完整的代码，主要是先把算法过一遍，了解一下优化的算法，开拓一下思维。