您现在的位置是：首页 >技术教程 >day 3 | 203.移除链表元素、707.设计链表、206.反转链表网站首页技术教程
day 3 | 203.移除链表元素、707.设计链表、206.反转链表
简介day 3 | 203.移除链表元素、707.设计链表、206.反转链表
目录：
学习链接
链表基础：https://programmercarl.com/链表理论基础.html
题目链接：
https://leetcode.cn/problems/remove-linked-list-elements/
解题及思路学习
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
自己思路：从头节点遍历整个链表，然后依次查看其中数据是否等于val，如果等于，则进行删除操作。
随想录思路：对于头节点是否删除，是两种不同的写法，所以需要进行判断。但是也可以增加一个虚拟头节点，以统一的方式操作进行，提高代码简洁性。
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点。（代码中使用了一个临时节点，来进行释放内存操作）。
（1）对于头节点分开判断
/**
* 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;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
(2) 设置一个虚拟节点进行移除操作
/**
* 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; // 将虚拟头结点指向head，这样方便后面做删除操作
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;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
注意虚拟头节点的设置，可以很大程度上方便单链表操作。另外，C++记得即使清理内存。
707. 设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
思路：根据要求写链表。为了统一化操作，可以设置一个虚拟头节点。
随想录思路：
class MyLinkedList {
public:
//定义链表节点结构体
struct LinkNode {
int val;
LinkNode* next;
LinkNode(int val): val(val), next(nullptr){}
};
LinkNode* _dummyHead;
int _size;
//初始化链表
MyLinkedList() {
_dummyHead = new LinkNode(0);
_size = 0;
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if(index > (_size -1) || index < 0 ){
return -1;
}
LinkNode* cur = _dummyHead -> next;
while(index--){
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkNode* newNode = new LinkNode(val);
newNode -> next = _dummyHead -> next;
_dummyHead -> next = newNode;
_size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkNode* newNode = new LinkNode(val);
LinkNode* 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;
LinkNode* cur = _dummyHead;
LinkNode* newNode = new LinkNode(val);
while(index){
cur = cur -> next;
index--;
}
newNode -> next = cur -> next;
cur -> next = newNode;
_size++;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
void deleteAtIndex(int index) {
if(index >= _size || index < 0){
return;
}
LinkNode* cur =_dummyHead;
while(index--){
cur = cur -> next;
}
LinkNode* tmp = cur -> next;
cur -> next = cur -> next -> next;
delete tmp;
//delete命令指示释放了tmp指针原本所指的那部分内存，
//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=nullptr;
_size--;
}
};
/**
* 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);
*/
- 时间复杂度: 涉及
index的相关操作为 O(index), 其余为 O(1) - 空间复杂度: O(n)
代码随想录代码：
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后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=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;
};
创建的dummyHead 需要用new 开辟空间 ，不用new的话就只是一个listnode指针。
随想录给出的示例中，初始化链表部分，为什么不需要提前声明？但是也能运行。
我自己写的代码中，不提前声明就不行。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dKOwzvwC-1685194194015)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7c3ffea4-67e8-45bd-b8a6-7e6305d3a30f/Untitled.png)]
原因：代码后面的私有属性那里有命名。
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ygtd47oV-1685194194018)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/9b444690-a882-4c09-889d-a761fefedfae/Untitled.png)]
自己思考：可以在创建一个新的链表，用虚拟头节点。每次读取到一个节点，就在新的链表上开始位置添加一个节点。遍历完之后就实现了反转。
自己实现的代码：
/**
* 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* dummyHead = new ListNode(0);
ListNode* dummyHead1 = new ListNode(0);
dummyHead -> next = head;
ListNode* cur = dummyHead;
while(cur->next != nullptr){
ListNode* newNode = new ListNode(0);
newNode -> val = cur -> next -> val;
newNode -> next = dummyHead1 -> next;
dummyHead1 -> next = newNode;
cur = cur-> next;
}
delete dummyHead;
head = dummyHead1 -> next;
delete dummyHead1;
return head;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(n)
代码随想录idea：不需要再开辟空间，只要把指针反一下。利用三个指针可以做到。https://programmercarl.com/0206.翻转链表.html#双指针法
/**
* 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* temp; // 保存cur的下一个节点
ListNode* pre = NULL;
ListNode* cur = head;
while(cur){
temp = cur -> next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur -> next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
困难及收获
困难
1、链表的定义，增删改查
2、单链表虚拟头节点的思想
今日收获
双指针真是个好东西。
C++得多注意内存，释放空间。
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述