day03 移除链表元素 设计链表 反转链表
发布时间：2024年01月03日
题目1：203 移除链表元素
题目链接：203 移除链表
题意
删除链表中所有满足Node.val==val的节点? ?返回新的头节点
注意使用cur临时指针，遍历链表，这样才可以最终返回head，不可以拿着head去遍历，否则，头节点会改变，无法返回整个链表
分类讨论
代码
/**
* 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)
虚拟头节点
本题使用虚拟头节点方法? 更优，这样不用分类讨论，可以统一操作
代码
/**
* 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;
//定义临时指针cur,遍历链表
ListNode *cur = dummyhead;
//遍历所有的链表节点
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 dummyhead->next;//注意返回的dummyhead一定是新链表的头节点
}
};- 时间复杂度: O(n)
- 空间复杂度: O(1)
题目2：707 设计链表
题目链接：707 设计链表
题意
链表实现如下功能：
①初始化节点
②获取链表的某个节点值? （index从0开始，head的index为0）
③在头节点前面插入一个节点
④在尾节点后面插入一个节点
⑤在第n个节点处插入一个节点
⑥删除第n个节点
代码
①初始化节点
//定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val),next(nullptr){} //没有分号
};
//初始化链表
MyLinkedList() {
dummyhead = new LinkedNode(0);
size_ = 0;
}②获取链表的某个节点值? （index从0开始，head的index为0）
法1：cur指向dummyhead
代码1
int get(int index) {
if(index<0 || index>(size_-1)) return -1;
LinkedNode* cur = dummyhead;
while(index){
cur = cur->next;
index--;
}
return cur->next->val;
}法2：cur指向dummyhead->next
代码2
int get(int index) {
if(index<0 || index>(size_-1)) return -1;
LinkedNode* cur = dummyhead->next;
while(index){
cur = cur->next;
index--;
}
return cur->val;
}③在头节点前面插入一个节点
注意插入的节点顺序，这非常关键，这也是“坑”
代码
void addAtHead(int val) {
LinkedNode* newnode = new LinkedNode(val);
newnode->next = dummyhead->next;
dummyhead->next = newnode;
size_ ++;//注意添加了元素，要在原链表的基础上加1
}④在尾节点后面插入一个节点
注意while循环的条件是cur->next!=NULL 不能是size_
代码
void addAtTail(int val) {
LinkedNode* cur = dummyhead;
LinkedNode* newnode = new LinkedNode(val);
while(cur->next!=nullptr){
cur = cur->next;
}
cur->next = newnode;
size_++;//添加了元素，链表大小加1
}！！！错误代码（如果使用size_做循环操作，那么意味着表示链表大小的量size_会发生变化，不能拿代表真实的链表大小了）
void addAtTail(int val) {
LinkedNode* cur = dummyhead;
LinkedNode* newnode = new LinkedNode(val);
while(size_){
cur = cur->next;
size_--;
}
cur->next = newnode;
size_++;//添加了元素，链表大小加1
}如果想要使用这个量用于while循环的条件判定，可以将size_赋值给一个新变量n，代码如下，这时，代码就是正确的了
void addAtTail(int val) {
int n = size_;
LinkedNode* cur = dummyhead;
LinkedNode* newnode = new LinkedNode(val);
while(n){
cur = cur->next;
n--;
}
cur->next = newnode;
size_++;//添加了元素，链表大小加1
}⑤在第n个节点处插入一个节点
注意“坑”? ? ? ?：即顺序??
在第n个节点处插入一个节点，因此一定要知道第n-1个节点，所以cur=dummyhead
代码
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;
index--;
}
newnode->next = cur->next;
cur->next = newnode;
size_++;//新加入了节点，链表大小要加1
}⑥删除第n个节点
删除第n个节点，一定要知道第n-1个节点，因此，cur=dummyhead
代码
void deleteAtIndex(int index) {
if(index>(size_-1)||index<0) return;
LinkedNode* cur = dummyhead;
while(index){
cur = cur->next;
index--;
}
//注意释放内存
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp = nullptr;
size_--;//删除了一个元素，链表大小减1
}整体代码
class MyLinkedList {
public:
//定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val),next(nullptr){} //没有分号
};
//初始化链表
MyLinkedList() {
dummyhead = new LinkedNode(0);
size_ = 0;
}
int get(int index) {
if(index<0 || index>(size_-1)) return -1;
LinkedNode* cur = dummyhead;
while(index){
cur = cur->next;
index--;
}
return cur->next->val;
}
void addAtHead(int val) {
LinkedNode* newnode = new LinkedNode(val);
newnode->next = dummyhead->next;
dummyhead->next = newnode;
size_ ++;//注意添加了元素，要在原链表的基础上加1
}
void addAtTail(int val) {
LinkedNode* cur = dummyhead;
LinkedNode* newnode = new LinkedNode(val);
while(cur->next!=nullptr){
cur = cur->next;
}
cur->next = newnode;
size_++;//添加了元素，链表大小加1
}
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;
index--;
}
newnode->next = cur->next;
cur->next = newnode;
size_++;//新加入了节点，链表大小要加1
}
void deleteAtIndex(int index) {
if(index>(size_-1)||index<0) return;
LinkedNode* cur = dummyhead;
while(index){
cur = cur->next;
index--;
}
//注意释放内存
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp = nullptr;
size_--;//删除了一个元素，链表大小减1
}
void printLinkedList() {
LinkedNode* cur = dummyhead;
while(cur->next!=nullptr){
cout<<cur->next->val<<" ";
cur = cur->next;
}
cout<<endl;
}
private:
int size_;
LinkedNode* dummyhead;
};
/**
* 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)? 其中 n?为链表的长度。需要为每个节点分配内存空间来存储节点的值和下一个节点的指针，并且还需要一个额外的虚拟头节点指向链表的头部。
题目3：206 反转链表（面试高频）
题目链接：206 反转链表
题意
根据链表的头节点head? 返回反转后的链表
双指针
代码
/**
* 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* pre = NULL;
ListNode* cur = head;
while(cur!=NULL){
ListNode* temp = cur->next;
cur->next = pre;
//pre，cur向后移动一位
pre = cur;
cur = temp;
}
return pre;
}
};- 时间复杂度: O(n)
- 空间复杂度: O(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* reverse(ListNode* cur, ListNode* pre){
//终止条件
if(cur==NULL) return pre;
//单层递归逻辑
ListNode* temp = cur->next;
cur->next = pre;
return reverse(temp,cur);
}
ListNode* reverseList(ListNode* head) {
return reverse(head,NULL);
}
};- 时间复杂度: O(n), 要递归处理链表的每个节点
- 空间复杂度: O(n), 递归调用了 n 层栈空间
文章来源:https://blog.csdn.net/qq_43773652/article/details/135352082
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 软件需求分析期末复习题【包含答案】（持续更新中...）
- DFS,BFS算法
- 【每日试题】精选Java面试题八股文
- 【LeetCode每日一题】2788. 按分隔符拆分字符串
- 《设计模式的艺术》笔记 - 状态模式
- SQL分类
- Python | Iter/genartor | 一文了解迭代器、生成器的含义\区别\优缺点
- vue3中Fragment特性的一个bug，需要留意的注意事项
- 软件仓库部署及应用
- 动态规划Day12(股票问题终结,有点疑惑)