一、移除链表元素的思想
直接让前一个节点指向后一个节点即可
两种方法
第一种:直接删除
第二种:头删的时候,直接head=head->next
其实这两种方法都没有做到统一
第三种:虚拟头结点法
这样的话,咱们删除的时候,就是以统一的规则来进行删除啦!
二、203.移除链表元素
203.移除链表元素
法一:原始删除法
class Solution
{
public:
ListNode *removeElements(ListNode *head, int val)
{
// 头删
while (head != nullptr && head->val == val)
{
ListNode *tmp = head;
head = head->next;
delete tmp;
}
// 接下来不是头删,正常的中间删除
ListNode *cur = head;
while (cur != nullptr && cur->next != nullptr)
{
if (cur->next->val == val)
{
ListNode *tmp = cur->next;
cur->next = cur->next->next;
delete tmp; // 内存释放
}
else
{
cur = cur->next;
}
}
return head;
}
};
1、while(head!=nullptr && head->val == val)?
注意使用while 而不是 if ,因为会有特殊情况,持续删除头结点的情况,所以使用外while。
2、if(cur->next->val==val)
我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话,我们是不好来找到当前节点的上一个节点,从而链接起来的。
法二:虚拟头结点法
class Solution
{
public:
ListNode *removeElements(ListNode *head, int val)
{
// 虚拟头结点来删除
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = dummy; // 为啥从dummy起始?
while (cur->next != nullptr)
{
if (cur->next->val == val)// 为啥用cur->next->val 作为判断?
{
cur->next = cur->next->next;
}
else
{
cur = cur->next;
}
}
return dummy->next;
}
};
1、ListNode *cur = dummy; // cur为啥从dummy起始?
而不是cur=head?
我们删除链表元素一定要知道上一个元素的指针是啥,我们删的是cur->next->val。
2、while (cur->next != nullptr)
遍历的时候,我们要判断的是cur->next->val,所以我们while (cur->next != nullptr) 要这么写。
3、if (cur->next->val == val)// 为啥用cur->next->val 作为判断?
我们是使用的cur的next的值来判断是不是我们想要删除的val的。如果我们直接使用cur的值来判断的话,我们是不好来找到当前节点的上一个节点,从而链接起来的。
4、为啥return dummy->next;
因为return head;有可能head已经被删除了。
三、707.设计链表
707.设计链表
统一使用虚拟头结点的方式,让我们的操作统一化。
我们还需要一个虚拟头节点_dummy
作为头节点,和一个_size
参数保存有效节点数。注意题目下标从0开始。
一定要注意:我们的临时变量定义cur=_dummy
,操作的是cur->next,这样我才能方便的增加、删除,这才是对应到我们的第index(或者说第n个节点)。
class MyLinkedList
{
public:
// 定义链表节点结构体
struct ListNode
{
int val;
ListNode *next;
ListNode(int val) : val(val), next(nullptr) {}
};
MyLinkedList()
{
// 定义虚拟头结点
_dummy = new ListNode(-1);
_size = 0;
}
// 获取到第index个节点数值,如果index是非法数值直接返回-1, 注意index是从0开始的,第0个节点就是头结点
// 注意 index和_size差值为1
int get(int index)
{
if (index > (_size - 1) || index < 0)
{
return -1;
}
ListNode *cur = _dummy->next; // 从头开始遍历寻找
// 注意下标从0开始
while (index)
{
cur = cur->next;
index--;
}
return cur->val;
}
void addAtHead(int val)
{
ListNode *newnode = new ListNode(val);
// 这两步顺序不能交换
newnode->next = _dummy->next;
_dummy->next = newnode;
_size++;
}
void addAtTail(int val)
{
ListNode *newnode = new ListNode(val);
// 找尾
ListNode *cur = _dummy; // 为啥从dummy开始?
while (cur->next != nullptr)
{
cur = cur->next;
}
cur->next = newnode;
_size++;
}
// 如果index大于链表的长度,则返回空
// 如果index小于0,则在头部插入节点
void addAtIndex(int index, int val)
{
if (index > _size)
return;
if (index < 0)
index = 0;
// 一定要找到第index个节点的前驱
ListNode *newnode = new ListNode(val);
ListNode *cur = _dummy;
// 遍历找到第n个节点
while (index--)
{
cur = cur->next;
}
// 这下面两步顺序也是不能换的
newnode->next = cur->next;
cur->next = newnode;
_size++;
}
void deleteAtIndex(int index)
{
if (index < 0 || index >= _size)
{
return;
}
ListNode *cur = _dummy;
// 遍历找到第n个节点
while (index--) // 当index=0时,while循环就不会执行了
{
cur = cur->next;
}
ListNode *tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp = nullptr;
_size--;
}
private:
int _size;
ListNode *_dummy;
};
1、头插顺序不能变
2、addAtTail 中ListNode * cur=_dummy;// 为啥从dummy开始?
因为有可能刚刚开始没有元素,相当于在dummy后插入。
3、注意index与size之间的关系,他们差值为1
四、206.反转链表
206.反转链表
面试中经常出现
双指针法
// 双指针
class Solution
{
public:
ListNode *reverseList(ListNode *head)
{
ListNode *cur = head;
ListNode *pre = nullptr;
while (cur != nullptr)
{
ListNode *tmp = cur->next;
cur->next = pre; // 反转操作
// 下面两步不能换顺序
pre = cur;
cur = tmp;
}
return pre;
}
};
1、为啥要这样初始化?
因为这样初始化,直接让咱们的反转后的尾节点直接执行nullptr了。
2、while( ? ) 循环结束调条件是啥
就是cur为空就结束了,最后一步,不再需要nullptr指向pre了,没有意义。while(cur)就行了。
3、为啥需要每次进入循环都要定义一个tmp临时变量?
因为这样可以方便更新cur,反转后,cur无法后移指向下一个节点,tmp保存cur->next,趁着pre和cur还连着的时候先保存下来,然后就可以赋值了,一定要先移pre,后移动cur。
递归法
class Solution
{
public:
// 子函数
ListNode *reverse(ListNode *cur, ListNode *pre)
{
if (cur == nullptr)
return pre; // 2.终止条件就是cur指向nullptr
ListNode *tmp = cur->next;
cur->next = pre; // 3.反转操作
return reverse(tmp, cur); // 4、进入下一层循环(递归) 谁赋值给cur? 谁赋值给pre?
}
ListNode *reverseList(ListNode *head)
{
return reverse(head, nullptr); // 1.head赋值给cur,nullptr赋值给pre
}
};
从后往前翻转指针指向 递归文章来源:https://www.toymoban.com/news/detail-598953.html
- 使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点,记作last
- 此后,每次函数在返回的过程中,让当前结点的下一个结点的next指针指向当前节点。
- 同时让当前结点的neat指针指向NULL,从而实现从链表尾部开始的局部反转
- 当递归函数全部出栈后,链表反转完成。
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;
}
};
文章来源地址https://www.toymoban.com/news/detail-598953.html
到了这里,关于代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!