动漫网站开发 sh框架,珠海网站建设培训,做网站获取ip,学做网站论坛课程目录
一、链表
基础操作
二、#xff08;leetcode 203#xff09;移除链表元素
1.使用原来的链表
2.设置虚拟头结点
三、#xff08;leetcode 707#xff09;设计链表
四、#xff08;leetcode 206#xff09;反转链表
1.双指针法
2.递归法 一、链表
单链表定义…目录
一、链表
基础操作
二、leetcode 203移除链表元素
1.使用原来的链表
2.设置虚拟头结点
三、leetcode 707设计链表
四、leetcode 206反转链表
1.双指针法
2.递归法 一、链表
单链表定义
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
}; 基础操作
1删除节点 2 添加节点 注意最后一个节点的删除通过next指针进行删除操作
二、leetcode 203移除链表元素
力扣题目链接 状态设置虚拟头结点方法AC在原链表上直接操作待回顾 思路
链表的其他节点是通过前一个节点来移除当前节点头结点的移除是将头结点向后移动一位设置一个虚拟头结点移除后return dummyNode-next 1.使用原来的链表
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点while (head ! NULL head-val val) { // 注意这里不是if一串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;}
};
2.设置虚拟头结点
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyheadnew ListNode(0);//设置虚拟头节点dummyhead-nexthead;ListNode* cur dummyhead;while (cur-next ! NULL) {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;}
};
三、leetcode 707设计链表
力扣题目链接 状态其他功能已清楚deleteAtIndex需要待看 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后//如果不再加上一句tmpnullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp会指向难以预想的内存空间tmpnullptr;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur _dummyHead;while (cur-next ! nullptr) {cout cur-next-val ;cur cur-next;}cout endl;}
private:int _size;LinkedNode* _dummyHead;};
四、leetcode 206反转链表
力扣题目链接 状态双指针法AC递归法捋完思路AC、待回顾 1.双指针法
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur head;ListNode* pre NULL;while(cur) {temp cur-next; // 保存一下 cur的下一个节点因为接下来要改变cur-nextcur-next pre; // 翻转操作// 更新pre 和 cur指针pre cur;cur temp;}return pre;}
};
2.递归法
递归解题三部曲
找整个递归的终止条件递归应该在什么时候结束找返回值应该给上一级返回什么信息本级递归应该做什么在这一级递归中应该完成什么任务
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);}};
