C++刷题笔记(6)——leetcode203、707、206

2024-02-02 19:32
文章标签 c++ 笔记 刷题 206 707 leetcode203

本文主要是介绍C++刷题笔记(6)——leetcode203、707、206，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表理论基础

1.list容器
2.关于链表，你该了解这些！
3.C++ list（STL list）容器完全攻略

题目1：203.移除链表元素

在这里插入图片描述
解题思路：
以链表 1 4 2 4 来举例，移除元素4。
在这里插入图片描述
但是如果删除的是头节点，移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点，因此需要用新的方法：

解法一：设置一个虚拟头结点在进行删除操作

在这里插入图片描述
给链表添加一个虚拟头结点为新的头结点，移除这个旧头结点元素1。

在C++中还要从内存中删除移除后的节点

 class Solution {public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);         // 初始化一个空节点，初始值为0，指针指向dummyheaddummyHead->next = head;                        // 将虚拟头结点指向head   上面两句也可以写成:ListNode* dummyHead = new ListNode(0,head)ListNode* cur = dummyHead;                     // 定义一个临时指针，等于虚拟头节点，用来代替虚拟头节点遍历链表(如果用虚拟头节点遍历链表，其值会不停变化，最后不好确定返回值)while (cur->next != NULL) {                    // 临时指针的下一个节点不为空if (cur->next->val == val) {               // 当指针的下一个节点的值等于目标值ListNode* tmp = cur->next;             //定义一个指针指向临时指针指向的节点(可以不写)cur->next = cur->next->next;           // 指针指向下下个值delete tmp;                            // 删除 cur->next}else {cur = cur->next;                       // 指针向后移动遍历指针}}head = dummyHead->next;                        // 重新定义头节点delete dummyHead;                              // 对虚拟头节点进的空间进行释放，防止内存泄漏return head;}};

解法二：直接使用原来的链表来进行删除操作

在这里插入图片描述
要将头结点向后移动一位
在这里插入图片描述
将原头结点从内存中删掉
在这里插入图片描述

 class Solution {public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点，注意这里不是if，因为可能新的头节点指向的值也等于目标值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;}};

解法三：双指针法

评论区大佬给出了五种解法：移除链表元素(五种方法)
这里再记录一种双指针法，这位up也讲解的非常清晰：203.移除链表元素

题目2：707.设计链表

在这里插入图片描述

解法一：单链表

解题思路：
起始这一题看着很长，但主要还是那几行代码的堆叠，只要把那几行代码理解了就不难

以addAtIndex(index,val)为例：
假设链表为1->3->5->7->9，现在要在第2个节点之前插入一个新节点(addAtIndex(2,4))
在这里插入图片描述
那么首先新定义一个节点并赋值，然后将定义虚拟头节点指针
在这里插入图片描述
然后开始遍历index之前的链表:
在这里插入图片描述
然后执行newNode->next = cur->next;
在这里插入图片描述
执行cur->next = newNode;size++;
在这里插入图片描述
其他几种和这个也是差不多的
代码不难，但是要注意定义的临时指针cur什么时候指向虚拟头节点dummyhead、什么时候指向虚拟头节点的下一个节点dummyhead->next

 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) {           //输入的index不在范围内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大于链表的长度，则返回空//void addAtIndex(int index, int val) {//    if (index <= 0) {//        addAtHead(val);//    }//    else if (index == size) {//        addAtTail(val);//    }//    else if (index > size) {//        return;//    }//    else {//        LinkedNode* newNode = new LinkedNode(val);//        LinkedNode* cur = dummyHead;//        while (index--) {//            cur = cur->next;//        }//        newNode->next = cur->next;//        cur->next = newNode;//        size++;//    }//}void addAtIndex(int index, int val) {if (index > size) {                            //大于链表长度返回空return;}     LinkedNode* newNode = new LinkedNode(val);     //包含了等于链表长度的情况LinkedNode* cur = dummyHead;while (index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接returnvoid 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;size--;}// 打印链表void printLinkedList() {LinkedNode* cur = dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}private:int size;LinkedNode* dummyHead;};

解法二：双链表

class ListsNode
{
public:int val;ListsNode* next;ListsNode* pre;ListsNode(int v, ListsNode* n, ListsNode* p):val(v),next(n),pre(p){}
};class MyLinkedList {
public:ListsNode* root;ListsNode* trail;int size;/** Initialize your data structure here. */MyLinkedList() {root=nullptr;trail=nullptr;size=0;}/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */int get(int index) {int temp=0;ListsNode* cur=root;while(cur!=nullptr){if(temp==index){return cur->val;}cur=cur->next;temp++;}return -1;}/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */void addAtHead(int val) {if(root!=nullptr){ListsNode* newNode=new ListsNode(val, root, nullptr);root->pre=newNode;root=newNode;         }else{root=new ListsNode(val, nullptr,nullptr);trail=root;}size++;}/** Append a node of value val to the last element of the linked list. */void addAtTail(int val) {if(trail!=nullptr){ListsNode* newNode = new ListsNode(val, nullptr, trail);trail->next=newNode;trail=newNode;}else{trail=new ListsNode(val, nullptr, nullptr);root=trail;}size++;}/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */void addAtIndex(int index, int val) {if(index<=0){addAtHead(val);return;}if(index==size){addAtTail(val);return;}int temp=0;ListsNode* pre=nullptr;ListsNode* cur=root;while(cur!=nullptr){if(temp==index){ListsNode* newNode=new ListsNode(val, cur, pre);if(pre!=nullptr){pre->next=newNode;}cur->pre=newNode;size++;return;}pre=cur;cur=cur->next;temp++;}}/** Delete the index-th node in the linked list, if the index is valid. */void deleteAtIndex(int index) {int temp=0;ListsNode* pre=nullptr;ListsNode* cur=root;if(index==0){ListsNode* old=root;root=root->next;if(root!=nullptr){root->pre=nullptr;}delete old;size--;return;}if(index==size-1){ListsNode* old=trail;trail=trail->pre;if(trail!=nullptr){trail->next=nullptr;}delete old;size--;return ;}while(cur!=nullptr){if(temp==index){ListsNode* old=cur;if(pre!=nullptr){pre->next=cur->next;}if(cur->next!=nullptr){cur->next->pre=pre;}delete old;size--;return;}pre=cur;cur=cur->next;temp++;}}
};

题目3：206.反转链表

在这里插入图片描述

解法一：双指针法

解题思路：
只需要将链表的next指针的指向翻转
在这里插入图片描述
定义两个指针，cur指针指向头节点、pre指针指向null空指针；
然后将cur->next指向pre，移动两个指针；
当cur指向null，翻转结束。

 class Solution {public:ListNode* reverseList(ListNode* head) {ListNode* temp;                        // 保存cur的下一个节点ListNode* cur = head;                  // cur指针指向头节点ListNode* pre = NULL;                  // pre指针指向nullwhile (cur) {                          // 遍历链表temp = cur->next;                  // 保存cur的下一个节点，因为接下来要改变cur->nextcur->next = pre;                   // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}};

解法二：递归法

和双指针法的思路差不多

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

这篇关于C++刷题笔记(6)——leetcode203、707、206的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/671730。

相关文章

C++ 中的 if-constexpr语法和作用

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if（staticif）,：本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa
阅读更多...
C++中::SHCreateDirectoryEx函数使用方法

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1：创建单层目录示例 2：创建多级目录3. 关键注
阅读更多...
C++从序列容器中删除元素的四种方法

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque
阅读更多...
C++常见容器获取头元素的方法大全

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素（即第一个元素）是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa
阅读更多...
C++字符串提取和分割的多种方法

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示
阅读更多...
C++原地删除有序数组重复项的N种方法

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体：最多保留两次五、分析和代码实现5.1、问题分析5.
阅读更多...
C++ 各种map特点对比分析

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map（如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现：基于红黑
阅读更多...
C++中函数模板与类模板的简单使用及区别介绍

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中，模板是实现泛型编程
阅读更多...
利用Python和C++解析gltf文件的示例详解

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2