【LeetCode刷题日记】：设计链表全解析

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言前面由于忙着整理苍穹外卖耽搁了算法的学习进度有点慢了下一阶段主要学习算法再整顿一下准备开黑马点评了暂时先用算法过渡一下吧。设计链表题目背景LeetCode707在链表类中实现这些功能get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。题目答案//单链表 class MyLinkedList { class ListNode { int val; ListNode next; ListNode(int val) { this.valval; } } //size存储链表元素的个数 private int size; //注意这里记录的是虚拟头结点 private ListNode head; //初始化链表 public MyLinkedList() { this.size 0; this.head new ListNode(0); } //获取第index个节点的数值注意index是从0开始的第0个节点就是虚拟头结点 public int get(int index) { //如果index非法返回-1 if (index 0 || index size) { return -1; } ListNode cur head; //第0个节点是虚拟头节点所以查找第 index1 个节点 for (int i 0; i index; i) { cur cur.next; } return cur.val; } public void addAtHead(int val) { ListNode newNode new ListNode(val); newNode.next head.next; head.next newNode; size; // 在链表最前面插入一个节点等价于在第0个元素前添加 // addAtIndex(0, val); } public void addAtTail(int val) { ListNode newNode new ListNode(val); ListNode cur head; while (cur.next ! null) { cur cur.next; } cur.next newNode; size; // 在链表的最后插入一个节点等价于在(末尾1)个元素前添加 // addAtIndex(size, val); } // 在第 index 个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。 // 如果 index 等于链表的长度则说明是新插入的节点为链表的尾结点 // 如果 index 大于链表的长度则返回空 public void addAtIndex(int index, int val) { if (index 0 || index size) { return; } //找到要插入节点的前驱 ListNode pre head; for (int i 0; i index; i) { pre pre.next; } ListNode newNode new ListNode(val); newNode.next pre.next; pre.next newNode; size; } public void deleteAtIndex(int index) { if (index 0 || index size) { return; } //因为有虚拟头节点所以不用对index0的情况进行特殊处理 ListNode pre head; for (int i 0; i index ; i) { pre pre.next; } pre.next pre.next.next; size--; } }题目分析这是一个链表的基础操作题类似于在数组中的增删操作但是链表肯定是比数组要复杂一些的但是搞懂原理实际上也没什么太大的区别。我们在操作这些方法时通常要设置一个虚拟头节点不了解的我在前面详细讲解过了主要就是为了简化操作。获取链表第index个节点的数值由于链表没有数组的索引获取链表值的时候我们不能直接查询而是要从头开始遍历直到查询到我们需要的节点。在这里我们定义了虚拟头节点那这样来说的话我们是从0节点开始遍历也就是我们的虚拟头节点但是我们需要理解的是如果题目里要查询的index0这里的节点是链表的真正头节点而到我们这里用虚拟头结点的方法的话0节点就是虚拟头节点因此要查询题目中给的就是虚拟头节点之后的一个节点。最直观的例子head虚拟头 → 节点10 → 节点20 → 节点30 用户认为的index 0 1 2因此循环条件就需要index1虚拟头(内部0) → 真实节点A(题目0) → 真实节点B(题目1) → 真实节点C(题目2)想要题目index 0→ 走1 步想要题目index 1→ 走2 步想要题目index 2→ 走3 步所以题目要 index我们就从虚拟头往后走 index1 步然后从虚拟头节点开始遍历最后到index1返回我们需要查询的。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。题目解析因为我们设置了虚拟头节点就算我们在这里要在第一个元素之前插入一个节点也跟正常插入操作没有区别第一个头节点的特殊性已经被我们的虚拟头节点弱化了所有节点平级。在执行插入操作时我们只需要把需要把虚拟头节点的next给要插入的节点的next然后再把新插入的节点放在虚拟头节点的后面这样就完成插入操作这里需要注意的是顺序问题避免覆盖操作因为一个节点只能记录一个位置一般是从右往左进行操作。先连后面再连前面新节点先连旧头 → 虚拟头再连新节点void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。题目解析插入到链表的最后一个元素的后面head(虚拟头) → 节点1 → 节点2 → 节点3 → null ↑ 最后一个节点节点3节点 3是最后一个节点它的next指向nullnull不是节点只是标记 “后面没了”因此我们在操作的时候只需要找哪个节点的值等于null即可for循环遍历找到之后直接把cur.next给新节点null往后移动。ListNode cur head;head → 20 → 10 → null cur循环while (cur.next ! null)cur.next 20 ! null → cur 20cur.next 10 ! null → cur 10cur.next null → 停void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度那么该节点会被追加到链表的末尾。如果index比长度更大该节点将 不会插入 到链表中。题目解析我们先上来校验index是否合法之后我们就开始处理一般操作先要找到要插入节点的前驱节点不然插不进去会断链。逐行代码流程演示我们用这个链表当例子plaintexthead(虚拟头) → 10 → 20 → 30 → null size 3 index 编号 0 1 2现在执行addAtIndex(1, 99);意思在 index1 的位置插入 99第 1 步判断 index 合法if (index 0 || index size) { return; }index1在 0~3 之间 ✅ 合法第 2 步找前驱节点ListNode pre head; for (int i 0; i index; i) { pre pre.next; }我们要插 index1所以循环跑 1 次流程开始 pre headi0 → pre pre.next →pre 指向 10✅前驱找到了10第 3 步创建新节点ListNode newNode new ListNode(99);第 4 步插入和头插法一样第一步新节点先连后面newNode.next pre.next;pre.next 是 20所以plaintext99 → 20第二步前驱再连新节点pre.next newNode;plaintext10 → 99最终链表变成plaintexthead → 10 → 99 → 20 → 30 → null index 0 1 2 3第 5 步长度 1size;size 从 3 → 4void deleteAtIndex(int index)如果下标有效则删除链表中下标为index的节点。题目解析因为有虚拟节点不需要对index0特殊处理循环跑 index 次 → 找到要删除节点的前驱删除 index0 → 循环跑 0 次 → pre head删除 index1 → 循环跑 1 次 → pre 指向 index0删除 index2 → 循环跑 2 次 → pre 指向 index1删除 找前驱 → 跳过要删的节点找前驱 用 for 循环跑 index 次结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励