重庆广告公司网站建设,域名历史价格查询,外包公司排名前十,搭建网站服务器平台的三种方式目录 链表基础 链表的定义
203. 移除链表元素
题目
思路
代码
直接删除法
虚拟头结点辅助法
707. 设计链表
题目
思路
代码
206. 反转链表
题目
思路
代码
双指针法
递归法 链表基础
链表是一种通过指针串在一起的线性结构#xff0c;每个节点都由数据域和指…目录 链表基础 链表的定义
203. 移除链表元素
题目
思路
代码
直接删除法
虚拟头结点辅助法
707. 设计链表
题目
思路
代码
206. 反转链表
题目
思路
代码
双指针法
递归法 链表基础
链表是一种通过指针串在一起的线性结构每个节点都由数据域和指针域组成数据域存放节点数据指针域存放指向下一个节点的指针最后一个节点的指针指向null也即这个指针为空指针。 链表的定义
随想录中标准的单链表定义如下
struct ListNode {int val; // 数据域里的数据 ListNode *next; // 指针域里指向下个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数直接定义并初始化一个节点的数据域值为x
};ListNode* head new ListNode(5); // 通过自己定义的构造函数来初始化节点直接赋值为5 ListNode* head new ListNode();
head-val 5; // 使用默认的构造函数来初始化节点但是这里需要自己赋值 203. 移除链表元素
题目 思路
力扣里已经定义好了链表所以我们只需要使用ListNode* 来定义指针即可。
这道题需要我们删除和目标值相同的节点所以我们的思路简单粗暴一个一个比下去然后遇到就删除就是了但是这里有一个问题就是我们要如何删除一个节点呢其实很简单要删除一个节点分三步第一步定义一个指针指向该节点第二步将原本指向该节点的指针指向这个节点的下一个节点第三步删除我们新定义的这个指针同时把指针指向的节点也删了。
我们的代码有两种做法一种是直接开干将要删的节点分为头结点和中间节点头结点先删中间节点再用一个while语句来删另一种是设置一个虚拟头结点这样就不存在需要删除头结点的情况了只需要删除中间节点即可但是最后要注意返回的是我们定义的虚拟头结点的下一个节点指针。
代码
直接删除法
/*** 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;}
};
虚拟头结点辅助法
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy new ListNode(0);dummy-next head;ListNode* cur dummy;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 dummy-next;return head;}
};
707. 设计链表
题目
设计一个链表实现以下功能
获取元素表头添加元素表尾添加元素表中添加元素删除元素。
思路
这就是最简单的手搓链表了bushi在这里我们可以像上面那样给链表的前面添加一个虚拟头结点dummy这样就不用考虑对头结点的特殊情况了所有节点都一视同仁。
这就没什么思路不思路的了思想很简单实现是关键真正写出来并且一点错没有那就可以了具体实现就看下面的代码吧。
注意当你要开始复习链表的时候就照着这个代码多抄多背以后面试再也不用担心
代码
class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val) : val(val), next(nullptr){}};// 初始化链表MyLinkedList() {dummy new LinkedNode(0); // 定义一个虚拟头结点size 0; // 链表的初始长度为0}// 获取第index个节点数值如果index非法则直接返回-1index从0开始int get(int index) {if (index 0 || index size - 1) {return -1;}LinkedNode* cur dummy-next;while (index--) { // index可以看作数组下标cur是从下标为0的节点开始的所以这里循环index次没错cur cur-next;}return cur-val;}// 在链表前面插入一个节点插入完后新的节点称为链表的新头结点void addAtHead(int val) {LinkedNode* newNode new LinkedNode(val);newNode-next dummy-next;dummy-next newNode;size;}// 在链表最后添加一个节点void addAtTail(int val) {LinkedNode* newNode new LinkedNode(val);LinkedNode* cur dummy;while (cur-next ! nullptr) {cur cur-next;}cur-next newNode;size;}// 在链表中第index个节点前插入新节点void addAtIndex(int index, int val) {if (index size) return;if (index 0) index 0;LinkedNode* newNode new LinkedNode(val);LinkedNode* cur dummy;while (index--) {cur cur-next;}newNode-next cur-next;cur-next newNode;size;}// 删除第index个节点void deleteAtIndex(int index) {if (index size - 1 || index 0) {return;}LinkedNode* cur dummy;while (index--) {cur cur-next;}LinkedNode* tmp cur-next;cur-next cur-next-next;delete tmp;tmp nullptr;size--;}// 打印链表void print() {LinkedNode* cur dummy;while (cur-next ! nullptr) {cout cur-next-val ;cur cur-next;}cout endl;}
private:int size;LinkedNode* dummy;
};
206. 反转链表
题目 思路
反转链表就是从一个链表的第一个有效节点开始逐一移出原链表放到新链表的开头
这样虽然原链表是从前往后拿走节点但是新链表是从后往前一个一个加进去这就完成了反转。
代码
双指针法
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; // 此时cur这个节点的下一个是新链表的第一个节点pre cur; // 然后pre指针指向现在cur的这个结点cur temp; // cur指向原链表的下一个结点}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);}};
