第一题 203. 移除链表元素
题目:
思路分析:
我们要删除节点说白了就是将节点移除,将要删除的节点的前一个的next域移动到要删除节点的next域,我们可以这样写当我们运到我们要删除节点然后件他删除,那么怎么删除?我们可以直接让我们要删除的元素找不到。如果我们直接将我们要删除的节点删除那么我们就找不到我们的要删除节点的下一个节点所以我们要将我们的节点进行平移操作,我们平移肯定要早到我们要删除节点的上一个节点,而我们的链表是单向的所以我们不可能回到上一个节点所以我们定义的指针要指向上一个节点,所以我们要通过cur->next去确定我们要删除的节点,这个就是我们的思路。
一刷
一刷用了块的方法我们不断移动头节点当发现我们的头结点的下一位为我们我删除的值的时候循环将头结点更新,为什么要将头结点的删除和其他结点区分开来,因为我们的头结点可能为空,而尾结点的next域为空所以要将俩端区分。在头节点判断中我们将头结点使用一个指针去操作这样可以让保证我们的头结点始终是我们链表的头部,我们的头结点等于我们头结点的下一个值,也就是说当我们头节点尾我们要删除的值的时候我们要将头节点向后移动然后删除我们的p指针指向的上一个头节点的值为什么是这样因为我们的头节点已经更新了。else后面确定的是尾节点我们可以通过相同的方法去解决因为没有说明区别,然后就是我们对不是俩段节点的处理了,正常的节点移除操作,最后我们返回的我们的头节点
代码解析
上面的代码我们使用了虚拟头节点,在头节点的前面添加我们的虚拟头结点,用一个指针去操作然后用虚拟头结点固定我们要返回的结点,当我们的指针的下一位不为空我们就不断循环我们指针指向下一个的值等于cur我们就对下一个元数进行删除将中间结点删除
第二题 206. 反转链表
题目:
题目分析:
我们要进行链表的反转我们要用上双指针,其实这个可以说是对双指针的考核,无论是之前的滑动窗口还是KMP都是对指针的考核,我们要对双指针确定的区间进行判断,区间的范围要掌握,第一章的数组本质是对双指针和区间范围的考核,我们要定义区间的范围去使用同一遍历规则去进行循环要不然可能回出现各种问题。
这个是双指针版本代码:
上面的注释希望大家思考下然后写出递归版本代码
下面我给出递归版本代码:
大家可以常考一下好了下面就将来今天的重点了!!!
第三题 707. 设计链表,
题目:
思路分析:
我也不废话了直接放代码
class MyLinkedList {
public:
//初始化链表
MyLinkedList() {
this->size = 0;
this->head=new ListNode(0);//这个是虚拟结点
}
//获取到第index个结点数值,如果index是非法的数值直接返回-1,注意index是从0开始
int get(int index) {
if(index<0||index>=size){//判断下标是否合法如果不合法返回-1
return -1;//什么是合法就是判断的取的值是否在区间内
}
ListNode*cur = head;//头结点
for(int i=0;i<=index;i++){//不断循环到index的结点
cur = cur->next;
}
return cur->val;//返回index下面的值
}
void addAtHead(int val) {
addAtIndex(0,val);//既然都是增加结点那么调用我们增加结点的函数就可以
}
void addAtTail(int val) {
addAtIndex(size,val);//同理
}
//增加结点
//如果index个节点之前插入新节点,那么新插入的节点为链表的新头节点
//如果index等于链表的长度,则说明是新插入的节点为链表的尾结点
//如果index大于链表的长度,则返回为空
void addAtIndex(int index, int val) {
if(index>size){//如果索引值越界那么我们直接返回空即可
return ;
}
index = max(0,index); //我们的下标在取最大值防止我们的大小是负数,我们索引也是负数的情况
size++;//因为我们要增加一个结点所以我们就要将我们的长度加1
ListNode*pred = head;//创建一个一个指针去移动
for(int i=0;i<index;i++){
pred = pred->next;//移动到当前我们索引的位置的前一位
}
ListNode*toAdd = new ListNode(val);//然后我们又创建了一个结点去将这给结点增加到我们的要增加的位置
toAdd->next = pred->next;//我们这个新结点的指针指向下一位是我们当前要插入结点位置的指针指向下一位,
pred->next = toAdd;//然后将我们索引的位置的前一位指向我们的插入结点
}
void deleteAtIndex(int index) {//删除结点
if(index<0||index>=size){
return ;
}
size--;//因为我们删除了元素所以我们的长度要减
ListNode*pred = head;//我们创建指针去指向我们的结点
for(int i=0;i<index;i++){//不断将我的结点移动到我们要删除元素的下一位然后退出循环
pred = pred->next;
}
ListNode*p=pred->next;//这个p指向的就是我们要删除的结点
pred->next = pred->next->next;//我们将结点的指向修改然后删除p指向的结点即可
delete p;
}
private://定义一个私有属性
int size;
ListNode*head;
};
这个可不盖的代码比较复杂都是对链表的基础操作,反正我是要背的
下面我给出c语言版本代码供大家参考:
class MyLinkedList {
public:
MyLinkedList() {
this->size = 0;
this->head=new ListNode(0);
}
int get(int index) {
if(index<0||index>=size){
return -1;
}
ListNode*cur = head;
for(int i=0;i<=index;i++){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0,val);
}
void addAtTail(int val) {
addAtIndex(size,val);
}
void addAtIndex(int index, int val) {
if(index>size){
return ;
}
index = max(0,index);
size++;
ListNode*pred = head;
for(int i=0;i<index;i++){
pred = pred->next;
}
ListNode*toAdd = new ListNode(val);
toAdd->next = pred->next;
pred->next = toAdd;
}
void deleteAtIndex(int index) {
if(index<0||index>=size){
return ;
}
size--;
ListNode*pred = head;
for(int i=0;i<index;i++){
pred = pred->next;
}
ListNode*p=pred->next;
pred->next = pred->next->next;
delete p;
}
private:
int size;
ListNode*head;
};
好了如果有什么不懂的在评论区留言,会解答的。
今天的分享到这里,如果喜欢这篇文章可以点个赞关注持续更新中…
