看到网站的第一印象,wordpress 微博登录注册,淘宝客建设网站需要哪些条件,vps云服务器203.移除链表元素 题目链接 | 文档讲解 |视频讲解 : 链接 1.思路#xff1a; 需要分情况讨论#xff1a;删除的是头元素 删除的是非头元素 删除头元素#xff0c;需要将头元素的下一个节点设置为新的头元素 删除非头元素#xff0c;得知道当前元素以及当前元素的下一个节…203.移除链表元素 题目链接 | 文档讲解 |视频讲解 : 链接 1.思路 需要分情况讨论删除的是头元素 删除的是非头元素 删除头元素需要将头元素的下一个节点设置为新的头元素 删除非头元素得知道当前元素以及当前元素的下一个节点需要将前一个节点的指针指向当前元素的下一个数据 2.代码
public ListNode removeElements(ListNode head, int val) {//删除的是头元素的情况,// 1.需要判断head!null,因为我们要比较首元素的值避免出现空指针// 2.不可使用if, eg7-7-7-7 val7,使用if在这种情况下就会漏判断while(head!null head.valval){headhead.next;}//指向头结点充当前置节点ListNode curhead;//需要判断当前元素以及下一个元素不为空因为我们需要删除的其实是下一个节点while (cur!null cur.next!null){if(cur.next.valval){//前置节点指向下下一个节点cur.nextcur.next.next;}else {//指向下一个节点curcur.next;}}//返回的是链表的入口//不能返回cur它只是一个辅助指针最后可能指向null,并不能代表整个链表return head;}
1.思路2 定义一个pre虚拟指针指向头结点 定义一个cur指针用于遍历数组寻找符合条件的数据并且它一开始指向的是pre,实际要删除的数据是cur.next 指向pre,这样删除头结点和删除非头结点的操作保持一样
2.代码 public ListNode removeElements(ListNode head, int val) {//定义一个前置节点ListNode prenew ListNode();//前置节点的指针指向头节点pre.nexthead;//当前节点指向前置节点ListNode curpre;//为什么不判断cur,因为在这个结构下cur不会为null,因为初始值是虚拟头节点且每次循环都可以保证cur!null//我们其实关注的是cur.next而不是curwhile(cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else{curcur.next;}}//返回链表的入口,即虚拟节点的下一个return pre.next;} 707.设计链表 题目链接 | 文档讲解 |视频讲解链接 1.思路
定义了一个虚拟节点DummyHead统一新增和删除操作index是从0开始的它指的是第一个有效节点不包含虚拟节点在index位置新增和删除元素时需要找到的操作元素的前一个元素我们遍历寻找的时候是从虚拟节点开始的所以index-1处就是前一个元素注意链表size的变化 ①向头部添元素新节点指针指向真实头节点虚拟头节点指针指向新新节点 ②向index从0开始位置添加元素 1首先判断下标的有效性 (链表有效区间 [0size-1],但是插入元素时size是有效区间相当于尾部插入元素无效区间 0 || size 2定义一个指针cur,for循环[0,index-1]找到index-1的位置节点指针变更 3【注】size ③向尾部添加元素: 1定义一个指针cur,找到尾部节点 while循环判断的是cur.next!null 2修改节点的指针 3size ④删除index从0开始位置元素: 1先判断index的有效性链表有效区间 [0,size-1] 2循环遍历到index-1的位置指针进行交换 3size-- 2.代码
class MyLinkedList {//1.定义一个指针class LinkedNode{int val;LinkedNode next;LinkedNode(){} LinkedNode(int val){this.valval;}}//1.链表的个数private int size;//2.虚拟头结点private LinkedNode head;public MyLinkedList() {this.size 0;//创建虚拟节点真实头结点是head.nextthis.head new LinkedNode(0);}//获取链表中某个元素 index从0开始且指向的是有效的链表节点不包含虚拟节点public int get(int index) {//先判断下标是否是有效的,下标是从0开始的所以链表的长度是size-1if(index0 || indexsize){return -1;}//定义一个指针指向虚拟头节点LinkedNode curhead;for(int i0;iindex;i){//指针后移curcur.next;}return cur.val; }//在头部添加元素public void addAtHead(int val) {//定义一个节点LinkedNode newNodenew LinkedNode(val);//先将新节点的指针指向虚拟头结点的下一个即链表的真实头节点newNode.nexthead.next;//虚拟头节点指向新节点head.nextnewNode;size;}//在尾部添加元素public void addAtTail(int val) {//定义一个新节点LinkedNode newNode new LinkedNode(val);//定义一个指针指向头节点LinkedNode curhead;//判断的是cur.nextwhile(cur.next!null){curcur.next;}//尾节点指向新节点cur.nextnewNode;//节点个数size;}//将一个值为 val 的节点插入到链表中下标为 index 的节点之前public void addAtIndex(int index, int val) {//【注】判断下标的合理性,链表的有效下标是[0,index-1],所以indexsize时相当于尾部添加元素if(index0 || index size){return;}LinkedNode newNode new LinkedNode(val);//从虚拟节点开始移动//dummyhead -1-2-3-null 假设index1,要在2元的前面新增节点所以cur指针要指向的是元素1LinkedNode curhead;//【注】index区间[0,index-1]for(int i0;iindex;i){curcur.next;}newNode.nextcur.next;cur.nextnewNode;size;}//删除某个元素public void deleteAtIndex(int index) {//判断下标的合理性if(index0 || index size){return;}LinkedNode curhead;//因为有虚拟头节点所以不用对index0的情况进行特殊处理//【注】从0开始有效下标是[0,index-1]找到的是其前置节点for(int i0;iindex;i){curcur.next;}//找到当前节点cur,指针指向当前节点的下一个cur.nextcur.next.next;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);*/ 206.反转链表 题目链接 | 文档讲解 |视频讲解链接 1.思路反转链表需要将原先的首节点变成尾节点首节点的指针指向null,原先的尾节点成为首节点中间节点的各个指针指向其上一个元素。采用 快慢指针实现 首先需要定义一个新的节点prenull充当慢指针 定义一个cur指针开始指向首节点充当快指针 这两个指针形成快慢指针cur指针总是比pre指针快一步pre是cur前置节点,要将cur指针的方向反转指向pre while循环操作中因为要修改cur指针的方向所以我们要先将cur指向的下一个节点先记录下来方便后续cur指针的后移 在进行翻转,慢指针先后移,快指针在后移 最终返回pre因为我们返回的是链表的入口此时cur指向了null,而pre才是指向反转链表后的首节点 2.代码
public ListNode reverseList(ListNode head) {//1.定义一个新节点充当慢指针ListNode pre null;//定义cur指针充当快指针ListNode curhead;while(cur!null){//记录当前节点的下一个方便下面cur的后移ListNode next cur.next;//指针指向前置节点指针反转cur.nextpre;//pre先指向cur,不可与下一步调转调转后快慢指针指向了同一个节点precur;//cur后移指向当前节点的下一个curnext;}//返回链表的入口此时cur指向null,pre指向原链表尾节点也就是反转后的首节点return pre;
}
总结链表中移除某个元素或者添加某个元素新增一个虚拟头结点来统一操作我们需要找到的是其前置节点注意链表个数的变化循环的判断条件 反转操作采用快慢指针
