热门标签
热门文章
- 1kafka消息丢失解决方案
- 2基于文心智能体平台打造专属情感类陪伴智能体【情绪价值提供者】_文心智能体 基础配置 开场白 人物设定 高级配置 知识库 数据库 召回配置
- 3web.xml中security-constraint配置测试
- 4python --moviepy合成视频加转场效果(淡入淡出),FFmepg,取首帧_moviepy 转场
- 5【SpringCloud】eureka 服务发现Discovery_res.discovery.type=eureka
- 6Qt QTabWidget详解
- 7【QT】QT 窗口（菜单栏、工具栏、状态栏、浮动窗口、对话框）_qt悬浮窗口
- 8Python快速实现一个域名、IP信息聚合网站_python ip聚合分析
- 9ubuntu 打开所有端口_ubuntu开启所有端口
- 10高级java开发工程师面试题之-----JVM篇_jvm高级面试
当前位置: article > 正文
day03打卡. 移除链表元素 and 设计链表 and 翻转链表
作者：繁依Fanyi0 | 2024-08-02 23:20:15
赞
踩
day03打卡. 移除链表元素 and 设计链表 and 翻转链表
移除链表元素
-
题意：删除链表中等于给定值 val 的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
-
力扣203题
思路一
直接使用原来的链表来进行移除节点操作：
-
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
-
移除头结点其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
/**
* 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* p,* q; //不能一开始就给p赋值为head，否则删除头结点后p依然指向的是原来的头结点
// 删除头结点
while (head != nullptr && head->val == val) { //注意判空，且不能使用if，否则只能删除一个头结点, eg: {7,7,7}
q= head;
head = head->next;
delete q;
}
// 删除非头结点
p = head;//将p指向新的头结点
while (p != nullptr && p->next != nullptr) { //对p和p的下一个元素进行判空,对下一个元素判空是因为防止p指向末尾时进入if，报空指针异常
if (p->next->val == val) {//当前p指向的要删除元素的前一个元素
q = p->next; //q指向被删除元素
p->next = q->next; //断开与q的连接，指向q的下一个元素
delete q; //释放结点空间
} else { //若没找到，p就继续向后移动
p = p->next;
}
}
return head;
}
};
-
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点
-
当然如果使用java ，python的话就不用手动管理内存了。
-
还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。
-
时间复杂度: O(n)
-
空间复杂度: O(1)
思路二
-
设置一个虚拟头结点在进行移除节点操作：
-
设置虚拟头结点指向原头结点，可以统一删除元素的方式，不同向上面一样单独删除头结点
-
最后呢在题目中，return 头结点的时候，别忘了
return dummyNode->next;， 这才是新的头结点
/**
* 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); // 设置一个虚拟头结点,并直接赋值初值为0;
dummyHead->next=head;// 将虚拟头结点指向head，这样方便后面做删除操作
ListNode * cur = dummyHead;
ListNode *q; //q用来释放被删元素空间
while(cur->next!=nullptr){
if(cur->next->val==val){
q=cur->next;
cur->next=q->next;
delete q;
}
else{
cur=cur->next;
}
}
return dummyHead->next; //返回虚拟头结点的下一个结点
}
};
-
时间复杂度: O(n)
-
空间复杂度: O(1)
设计链表
题意：
在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
-
-
力扣707题
这道题目设计链表的五个接口：
-
获取链表第index个节点的数值
-
在链表的最前面插入一个节点
-
在链表的最后面插入一个节点
-
在链表第index个节点前面插入一个节点
-
删除链表的第index个节点
思路一
-
设置一个虚拟头结点在进行操作,但是没有存入size变量记录链表长度
class MyLinkedList {
public:
typedef struct LinkedNode {
int val;
struct LinkedNode* next;
LinkedNode(int val, LinkedNode* next) : val(val), next(next) {} //赋予初值
} LinkedNode, *LinkedList;
MyLinkedList() { head = new LinkedNode(0, nullptr); } //初始化,head为虚拟头结点
int get(int index) {
LinkedList p = head->next; //p指向虚拟头结点的下一个结点
int count = 0;
while (p != nullptr && count < index) { //利用count找到index所对应的结点
p = p->next;
count++;
}
if (p == nullptr||count>index) {
return -1; // 或者抛出异常，表示索引越界或索引不合法
}
return p->val;
}
void addAtHead(int val) {
LinkedList newNode = new LinkedNode(val, nullptr); //建立新节点并进行赋值
newNode->next = head->next; //前插，注意顺序不能反
head->next = newNode;
}
void addAtTail(int val) {
LinkedList newNode = new LinkedNode(val, nullptr);//建立新节点并进行赋值
LinkedList p = head; //p指向虚拟头结点
while (p->next != nullptr) { //找到最后一个结点，并让p指向最后一个结点
p = p->next;
}
p->next = newNode; //直接进行后插
}
void addAtIndex(int index, int val) {
LinkedList newNode = new LinkedNode(val, nullptr);//建立新节点并进行赋值
int count = -1; //count等于赋值是代表虚拟头结点的索引值为-1，然后原本头结点的索引下标为0，
// 与index对应
LinkedList p = head;//p指向虚拟头结点
while (p!= nullptr && count < index - 1) { //找到索引下标为index的前一个结点，并让p指向
p = p->next; //p!= nullptr原因是index=表长的时候，可以将元素直接插入后面
count++;
}
if(p==nullptr||count>index-1){ //进行非法判断,index大于表长或小于1
return;
}
newNode->next = p->next; //进行前插操作，顺序不能反
p->next = newNode;
}
void deleteAtIndex(int index) {
LinkedList p = head;
int count = -1;//count等于赋值是代表虚拟头结点的索引值为-1，然后原本头结点的索引下标为0，
// 与index对应
while (p->next != nullptr && count < index - 1) { 找到索引下标为index的前一个结点，
p = p->next; //p->next != nullptr原因是index不能等于表长，否则对空指针进行操作,空指针异常
count++;
}
if (!(p->next) || count > index - 1) { //进行非法判断,index大于等于表长或小于1
return;
}
LinkedList q = p->next; //q用来记录index对应的结点，方便释放空间
p->next = q->next; //p的next指向q的next
delete q;
}
private:
LinkedNode * head; //私有化变量
};
/**
* 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);
*/
思路二
-
设置一个虚拟头结点在进行操作。
class MyLinkedList {
public:
typedef struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val, LinkedNode* next)
: val(val), next(next) {} // 赋予初值
LinkedNode(int val)
: val(val), next(nullptr) {} // 定义两个构造方法，方便赋值
} LinkedNode, *LinkedList;
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; // 进行非法判断
}
LinkedList cur = _dummyHead->next;
while (index--) { //写成--index就会陷入死循环（任何非零值都被视为 `true`） 且要保证第0个结点是cur才能在当前index结点进行操作
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedList newNode = new LinkedNode(val); // 建立新节点并进行赋值
newNode->next = _dummyHead->next; // 前插，注意顺序不能反
_dummyHead->next = newNode;
_size++; // 记录链表长度
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedList newNode = new LinkedNode(val); // 建立新节点并进行赋值
LinkedList cur = _dummyHead; // cur指向虚拟头结点
while (cur->next != nullptr) { // 找到最后一个结点，并让p指向最后一个结点
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;
LinkedList newNode = new LinkedNode(val); // 建立新节点并进行赋值
LinkedList cur = _dummyHead; // p指向虚拟头结点
while (index--) { //写成--index就会陷入死循环（任何非零值都被视为 `true`） 且要保证第0个结点是cur->next才能在前一个结点进行操作
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; // 非法判断
}
LinkedList cur = _dummyHead;
while (index--) { //写成--index就会陷入死循环（任何非零值都被视为 `true`） 且要保证第0个结点是cur->next才能在前一个结点进行操作
cur = cur->next;
}
LinkedList tmp = cur->next; // cur用来记录index对应的结点，方便释放空间
cur->next = tmp->next; // p的next指向q的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; // 私有化变量
};
/**
* 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)
翻转链表
-
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
-
力扣206题
思路一
-
也就是我的思路，不过在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* reverseList(ListNode* head) {
ListNode *Newhead=new ListNode();
ListNode *p=head;
while(p){
ListNode *q= new ListNode(p->val);
q->next=Newhead->next;
Newhead->next=q;
p=p->next;
}
return Newhead->next;
}
};
双指针法
-
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
-
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表
-
之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。
-
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点
/**
* 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 *cur = head;
ListNode *pre = nullptr;
ListNode * temp;// 保存cur的下一个节点
while(cur!=nullptr){
temp=cur->next;// 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next=pre;// 翻转操作
// 更新pre 和 cur指针
pre =cur;
cur=temp;
}
return pre;
}
};
递归法
-
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
-
关键是初始化的地方， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。
/**
* 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* cur = head;
// ListNode* pre = NULL;
return reverse(head, nullptr);
}
ListNode* reverse(ListNode* cur, ListNode* pre) {
if (cur == nullptr)
return pre;
ListNode* temp = cur->next; // 保存cur的下一个节点
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(temp, cur);
}
};
-
时间复杂度: O(n), 要递归处理链表的每个节点
-
空间复杂度: O(n), 递归调用了 n 层栈空间
其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 边缘条件判断
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 递归调用，翻转第二个节点开始往后的链表
ListNode *last = reverseList(head->next);
// 翻转头节点与第二个节点的指向
head->next->next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head->next = NULL;
return last;
}
};
-
时间复杂度: O(n)
-
空间复杂度: O(n)
本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签
