php网站开发外文,跨境电商交易平台,hexo到WordPress,搜了网推广文章目录 第一关—链表【青铜挑战】1.1 单链表的概念1.2 链表的相关概念1.3 创建链表 - Java实现1.4 链表的增删改查1.4.1 遍历单链表 - 求单链表长度1.4.2 链表插入 - 三种位置插入#xff08;1#xff09;在链表的表头插入#xff08;2#xff09;在链表的中间插入#… 文章目录 第一关—链表【青铜挑战】1.1 单链表的概念1.2 链表的相关概念1.3 创建链表 - Java实现1.4 链表的增删改查1.4.1 遍历单链表 - 求单链表长度1.4.2 链表插入 - 三种位置插入1在链表的表头插入2在链表的中间插入3在链表的结尾插入4在链表的所有位置插入[总结]⭐ 1.4.3 链表删除 - 三种位置删除1删除链表的表头结点2删除链表的最后一个结点3删除链表的中间结点4删除链表的任一位置[总结]⭐ 第一关—链表【青铜挑战】 1.1 单链表的概念
单向链表就像一个铁链一样元素之间互相连接包含多个结点每个结点**只有一个**指向后继元素的next指针并且最后一个元素的next指向null 小练以下两张图是否满足单链表的要求 解析 第一张图满足单链表的要求第二张图不满足要求因为c1它有两个后继结点a5和b4单链表的核心是一个结点只能有一个后继但是不代表一个结点只能有一个被指向如c1可以被a2和b3指向 注意做题的时候注意比较的是值还是结点有时可能两个结点的值是相等的但并不是同一个结点例如下图有两个结点的值都是1但并不是同一个结点 1.2 链表的相关概念
节点和头节点 在链表中每个点都由值和指向下一个节点的地址组成独立的单元成为一个结点有时也称为节点含义都是一样的 对于单链表而言如果知道了第一个元素就可以遍历访问整个链表因此第一个节点最重要一般称为头节点 虚拟结点 虚拟结点就是一个dummyNode其next指针指向head头部也就是dummyNode.next head 因此如果我们在算法里使用了虚拟结点则要注意如果要获得head结点或者从方法里返回的时候则应使用dummyNode.next 另外dummyNode的val不会被使用初始化为0或者-1等都是可以的既然值不会被使用那么我们就会有疑问虚拟结点有啥用呢简单来说就是为了方便我们处理头结点否则我们需要在代码里单独处理头结点【首部结点】的问题 1.3 创建链表 - Java实现 我们首先要理解JVM是怎么构建出链表JVM里面有栈区和堆区堆区主要存引用也就是一个指向实际对象的地址而堆区存的才是创建的对象 /*** Author Zan* Date 2023/11/29 14:46* Description : 传入一个数组将其转换成单链表*/
public class BasicLink {public static void main(String[] args) {int[] a {1, 2, 3, 4, 5, 6};Node head initLinkedList(a);System.out.println(head);}private static Node initLinkedList(int[] array) {Node head null, current null;for (int i 0; i array.length; i) {Node newNode new Node(array[i]);if (i 0) { // 头节点// 由于head current因此当current在变化的时候head也在变化head newNode;
// newNode new Node(array[i]); // 如果在此将newNode重新定义指向的是不同的堆数据因此head就只是一个Node普通对象单节点的链表current newNode;} else { // 后面的节点current.next newNode;current newNode;}}return head;}static class Node {public int x;public Node next;public Node(int x) {this.x x;next null;}}
}我们可以看到初始化链表的时候head和current指向的是同一个对象也就是指向堆中的同一个数据因此当控制current.next newNode 的时候其实就是控制堆中的数据指向谁next指向下一条数据而head跟current一样指向的是同一个对象因此就可以跟随其变化 最后得到head如下图所示 - 单链表的形式 1.4 链表的增删改查
对于单链表而言不管进行什么操作一定都是从头开始逐个向后开始访问所以操作之后是否还能够找到表头非常重要 1.4.1 遍历单链表 - 求单链表长度
/*** 遍历链表获取链表的长度* param head 头节点* return*/
public static int getListLength(Node head) { // 传入头节点int length 0;Node node head;while (node ! null) { // 一个一个节点遍历length;node node.next;}return length;
}1.4.2 链表插入 - 三种位置插入
单链表的插入和数组的插入一样过程不复杂。但是单链表的插入操作需要考虑三种情况首部、中部和尾部 1在链表的表头插入 创建新结点newNode新结点的next head即newNode.next head 头head指向新的链表即head newNode /*** 在链表的表头插入* param head 原链表* param nodeInsert 要插入表头的结点元素* return*/
public static Node insertNodeByHead(Node head, Node nodeInsert) {nodeInsert.next head;head nodeInsert;return head;
}2在链表的中间插入 循环找到要插入位置position的前一个结点位置从1开始将插入结点的next指向前一个结点的next即nodeInsert.next newNode.next 将前一个结点的next指向插入结点即newNode.next nodeInsert 注意我们不能先将前一个结点的next指向插入结点这是因为每个结点都只有一个next因此如果先将前一个结点的next指向插入结点那么15-7这一条线就断掉了也就导致后面的7、40将会找不到断开 /*** 在链表的中间位置插入* param head 原链表的头结点* param nodeInsert 要插入的结点* param position 要插入的位置从1开始* return*/
public static Node insertNodeByPosition(Node head, Node nodeInsert, int position) {Node newNode head; // 不对原链表进行操作用新链表指向堆中的同一个元素进行堆中的操作int i 1;while (i position - 1) { // 要在中间位置插入因此要获取插入位置的前一个结点这样子才能将next连接起来newNode newNode.next;i;}nodeInsert.next newNode.next; // 将要插入的结点的next指向插入位置前一个结点的nextnewNode.next nodeInsert; // 将插入位置前一个结点的next指向要插入的结点return head;
}3在链表的结尾插入 获取原链表总共有多少个元素循环遍历找到最后一个结点将最后一个结点的next指向新结点 /*** 在链表的结尾插入* param head 原链表的头结点* param nodeInsert 要插入的结点* return*/
public static Node insertByEnd(Node head, Node nodeInsert) {Node newNode head;int nodeLength getListLength(newNode); // 获取到原链表的元素个数int i 1;while (i nodeLength) { // 循环遍历找到最后一个结点newNode newNode.next;i;}newNode.next nodeInsert; // 将最后一个结点的next指向新结点return head;
}4在链表的所有位置插入[总结]⭐
/*** 链表的插入所有情况表头、中间、结尾** param head 原链表* param nodeInsert 插入的结点* param position 插入的位置从1开始* return*/
public static Node insertNode(Node head, Node nodeInsert, int position) {// head原链表中没有数据插入的结点就是链表的头结点if (head null) {return nodeInsert;}// 获取存放元素个数 - 进行校验(position在[1, size]之间)int size getListLength(head);if (position size 1 || position 1) {System.out.println(位置参数越界);return head;}// 表头插入if (position 1) {nodeInsert.next head;head nodeInsert;return head;}// 中间插入和结尾插入Node newNode head;int count 1;while (count position - 1) {count;newNode newNode.next;}nodeInsert.next newNode.next;newNode.next nodeInsert;return head;
}1.4.3 链表删除 - 三种位置删除
删除同样分为删除头部元素、删除中间元素和删除尾部元素 1删除链表的表头结点 将head表头向前移动一次之后原先的结点就变成了不可达会被JVM回收掉 /*** 删除表头结点* param head 原链表* return*/
public static Node deleteByHead(Node head) {head head.next;return head;
}2删除链表的最后一个结点 获取该链表的总长度size找到倒数第二个结点将倒数第二个结点的next指向null即newNode.next null /*** 删除最后一个结点* param head 原链表* return*/
public static Node deleteByEnd(Node head) {Node newNode head;int size getListLength(head); // 获取该链表的总长度sizeint i 1;while (i size - 1) { // 找到倒数第二个结点i;newNode newNode.next;}newNode.next null; // 将倒数第二个结点的next指向nullreturn head;
}3删除链表的中间结点 找到要删除结点的前一个结点将前一个结点的next指向下下个结点即newNode.next newNode.next.next /*** 删除中间结点* param head 原链表* return*/
public static Node deleteByPosition(Node head, int position) {Node newNode head;int i 1;while (i position - 1) {i;newNode newNode.next;}newNode.next newNode.next.next;return head;
}4删除链表的任一位置[总结]⭐
/*** 删除结点三种情况表头、中间、最后一位结点* param head 原链表* return*/
public static Node deleteNode(Node head, int position) {// 如果没有结点说明无法删除直接返回null即可if (head null) {return null;}//校验int size getListLength(head);if (position size || position 1) { // 这里不是size1而插入是size1因为插入可以插入到最后一位未知的最后一位而删除必须要是已知的不能是未知的越界System.out.println(输入的参数有误);return head;}if (position 1) { // 删除头节点return head.next;} else { // 删除中间结点或者最后一个结点Node newNode head;int count 1;while (count position - 1) {count;newNode newNode.next;}newNode.next newNode.next.next;return head;}
}
