代码随想录第三天-链表基础|203. 移除链表元素|707. 设计链表|206. 反转链表

[视频讲解](帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法_哔哩哔哩_bilibili)

链表基础

链表存放的数据和数组不同是非连续的

以下是c++制作链表的方法

#include <iostream>

class Soulution{
public:
    struct ListNode{
        int val;    //节点存储的值
        ListNode *next;     //指向下一个节点
        ListNode(int x):val(x),next(NULL){} //节点构造函数
        ListNode(int x,ListNode *next):val(x),next(next){}  //节点构造函数 可以提供快速连接功能
    };
    ListNode* removeElements(ListNode* head , int val){
        
    }

};

在操作时，着重要注意里面构造函数部分的操作，构造函数可以用悬空或多重构造。在主函数调用时按照需求进行初始化即可。

203. 移除链表元素

常规解法

简而言之：整个流程就是分为两块，头结点处理，中间节点处理，而进行删除操作时

注册中间tmp预备删除
把cur->next改成cur->next->next
删除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* removeElements(ListNode* head, int val) {
        while(head!= NULL&&head->val==val){
            //删除以及释放内存操作
            ListNode* tmp=head;
            head=head->next;
            delete tmp;
        }
        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;
    }

};

虚拟头结点法

第一遍敲完有一个空指针越界，排查问题进行修改

需要在循环位置对current->next进行判断是否为空指针

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode * V_Head_Node=new ListNode(0);
        V_Head_Node->next= head;
        ListNode *current =V_Head_Node;
        while(current->next!= NULL){
            if(current->next->val==val){
                ListNode *tmp =current->next;
                current->next=current->next->next;
                delete tmp;
            }
            else {
                current=current->next;
            }
        }
        return V_Head_Node->next;
    }
};

707.设计链表

一些注解

代码错误和修复

错误原因经过模拟一遍运行链表的运行过程可以分析得出：

void addAtIndex(int index, int val) {
    if (index > _size) return;
    LinkNode *newNode = new LinkNode(0);  // 错误地将新节点的值设置为0
    LinkNode *current = _v_Head;
    while (index--) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;  // 正确地链接新节点，但是新节点的值是0
}

初始化：
- 链表：[ ]
**addAtHead(1)**：
- 添加1到头部。
- 链表：[1]
**addAtTail(3)**：
- 添加3到尾部。
- 链表：[1, 3]
**addAtIndex(1, 2)**：
- 在索引1（第二个位置）添加值为2的节点。
- 链表：[1, 2, 3]
**get(1)**：
- 获取索引1（第二个位置）的元素，应该是2。
- 输出：2
**deleteAtIndex(1)**：
- 删除索引1（第二个位置）的节点。
- 链表：[1, 3]
**get(1)**：
- 再次获取索引1（第二个位置）的元素，现在应该是3。
- 输出：3

第二个错误经过排查发现是delete函数的更新写错了修正

void deleteAtIndex(int index) {
    if (index >= _size) {
        return;
    }
    LinkNode *current = _v_Head;
    while (index--) {
        current = current->next;
    }
    LinkNode *tmp = current->next;
    current = tmp->next;  // 这里错误地更新了 current，应该是 current->next = tmp->next
    delete tmp;
    tmp = nullptr;  
    _size--;
}

修正后还是报错，再此一步一步推导发现是get函数的边界条件有误

最终修正完成

206.翻转链表

链表的翻转是基于两个指针完成的，第一个指针是头指针，另外一个是尾指针，先不考虑tmp的去画通过两个指针拆断连接，重新构造连接的过程，最后再考虑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* current = head;
        ListNode* pre = nullptr;
        ListNode* tmp = nullptr;
        while(current!=NULL){
            tmp = current->next;  // 保存下一个节点
            current->next = pre;  // 反转指针
            pre = current;        // 前移pre
            current = tmp;        // 前移current
        }
        return pre;

    }
};

评价

第二题代码量上来，边界条件老是看不清楚，报错，查错非常费时费力，最好是提前对整体进行设计在旁边标注好边界条件，即可一次成功

代码随想录Day3