怎么在阿里巴巴网站做公司,巩义关键词优化公司电话,addfilter wordpress,做网站还有前景么数组和链表 数组 数组的特点是#xff1a;提供随机访问 并且容量有限。 假如数组的长度为 n。 访问#xff1a;O#xff08;1#xff09;//访问特定位置的元素 插入#xff1a;O#xff08;n #xff09;//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时…数组和链表数组数组的特点是提供随机访问并且容量有限。假如数组的长度为 n。访问O1//访问特定位置的元素插入On //最坏的情况发生在插入发生在数组的首部并需要移动所有元素时删除On//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时链表链表LinkedList虽然是一种线性表但是并不会按线性的顺序存储数据使用的不是连续的内存空间来存储数据。链表的插入和删除操作的复杂度为 O(1) 只需要知道目标位置元素的上一个元素即可。但是在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。//因为要访问的话需要从头开始访问著作权归JavaGuide(javaguide.cn)所有 基于MIT协议 原文链接https://javaguide.cn/cs-basics/data-structure/linear-data-structure.html单链表//单链表节点的构造publicclassSinglyLinkListNode{intdata;//负责保存节点中的数据SinglyLinkListNodenext;//指向写一个节点SinglyLinkListNode(intx){this.datax;//构造方法创建这个节点的对象把x放进data里}添加操作1.如果我们想在给定的结点 prev 之后添加新值我们应该使用给定值初始化新结点 cur将 cur 的 next 字段链接到 prev 的下一个结点 next 将 prev 中的 next 字段链接到 cur 。2.在开头添加节点众所周知我们使用头结点来代表整个列表。因此在列表开头添加新节点时更新头结点 head 至关重要。初始化一个新结点 cur 将新结点链接到我们的原始头结点 head。将 cur 指定为 head作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/j47r3/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。packagecom.javalearn.datastructure;//初始化节点publicclassSinglyLinkListNode{intdata;//节点里存的数据SinglyLinkListNodenext;//指向写一个节点SinglyLinkListNode(intx){datax;//构造方法创建这个节点的对象把x放进data里}}classtestA{//打印从t开始的链表publicstaticvoidprintList(SinglyLinkListNodet){SinglyLinkListNodecurrentt;while(current!null){System.out.println(current.data);currentcurrent.next;}System.out.println(链表遍历结束);}publicstaticvoidmain(String[]args){//初始化链表SinglyLinkListNodeheadnewSinglyLinkListNode(1);SinglyLinkListNodenode1newSinglyLinkListNode(2);SinglyLinkListNodenode2newSinglyLinkListNode(3);head.nextnode1;node1.nextnode2;node2.nextnull;System.out.println(head);//头插法SinglyLinkListNodenewHeadnewSinglyLinkListNode(0);newHead.nexthead;printList(newHead);//中间插SinglyLinkListNodemiddleNodenewSinglyLinkListNode(4);middleNode.nextnode1;head.nextmiddleNode;printList(newHead);}}删除操作1.如果我们想从单链表中删除现有结点 cur可以分两步完成找到 cur 的上一个结点 prev 及其下一个结点 next 接下来链接 prev 到 cur 的下一个节点 next 。在我们的第一步中我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next但是我们必须从头结点遍历链表以找出 prev它的平均时间是 O(N)其中 N 是链表的长度。因此删除结点的时间复杂度将是 O(N)。空间复杂度为 O(1)因为我们只需要常量空间来存储指针。2.删除第一个结点如果我们想删除第一个结点策略会有所不同。正如之前所提到的我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。如果想要删除第一个结点我们可以简单地将下一个结点分配给 head。也就是说删除之后我们的头将会是结点 6。3.//删除中间节点head.nextnode1;printList(newHead);//删除头节点newHeadhead;printList(newHead);作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/j1wom/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。设计链表publicclassMyLinkedList{publicclassNode{intdata;//节点里存的数据Nodenext;//指向写一个节点Node(intx){datax;//构造方法创建这个节点的对象把x放进data里}}Nodehead;intsize;publicMyLinkedList(){this.headnull;this.size0;}publicintget(intindex){if(index0||indexsize){return-1;}// 2. 空链表直接返回-1防御性判断if(headnull){return-1;}Nodecurrenthead;intnum0;while(num!index){currentcurrent.next;num;}returncurrent.data;}publicvoidaddAtHead(intval){//void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。NodenewNodenewNode(val);newNode.nexthead;headnewNode;size;}publicvoidaddAtTail(intval){//void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。NodenewNodenewNode(val);Nodecurrenthead;if(headnull){headnewNode;size;return;}else{while(current.next!null){currentcurrent.next;}current.nextnewNode;size;}}publicvoidaddAtIndex(intindex,intval){/* 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。 如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中 */Nodecurrenthead;NodenewNodenewNode(val);intnum0;if(index0||indexsize){return;}elseif(index0){addAtHead(val);}elseif(indexsize){addAtTail(val);}else{while(num!index-1){currentcurrent.next;num;}newNode.nextcurrent.next;current.nextnewNode;size;}}publicvoiddeleteAtIndex(intindex){//如果下标有效则删除链表中下标为 index 的节点。Nodecurrenthead;intnum0;if(index0||indexsize){return;}elseif(index0){headhead.next;size--;return;}else{while(num!index-1){currentcurrent.next;num;}current.nextcurrent.next.next;size--;}}}循环链表//判断链表是否成环//方法一建立快慢两个指针publicbooleanhasCycle(ListNodehead){if(headnull)returnfalse;//快慢两个指针ListNodeslowhead;ListNodefasthead;while(fast!nullfast.next!null){//慢指针每次走一步slowslow.next;//快指针每次走两步fastfast.next.next;//如果相遇说明有环直接返回trueif(slowfast)returntrue;}//否则就是没环returnfalse;}//方法二从头开始删除节点publicbooleanhasCycle(ListNodehead){//如果head为空或者他的next指向为空直接返回falseif(headnull||head.nextnull)returnfalse;//如果出现head.next head表示有环if(head.nexthead)returntrue;ListNodenextNodehead.next;//当前节点的next指向他自己相当于把它删除了head.nexthead;//然后递归查看下一个节点returnhasCycle(nextNode);}作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/jbex5/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。//如果不能更改链表publicListNodedetectCycle(ListNodehead){ListNodeslowhead,fasthead;//快慢指针相遇while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;//第一次相遇退出循环if(slowfast)break;}//判断是否有环if(fastnull||fast.nextnull)returnnull;//有环则将fast移动至head并移动S2距离fasthead;while(fast!slow){slowslow.next;fastfast.next;}returnfast;}作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/jjhf6/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。相交链表链表 - LeetBook - 力扣LeetCode全球极客挚爱的技术成长平台/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */publicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodep1headA;ListNodep2headB;// 核心逻辑两个指针同时遍历走到末尾后切换到另一个链表的头节点// 最终如果有交点p1和p2会在交点相遇如果没有交点会同时走到nullwhile(p1!p2){// p1走到末尾就切换到headB否则继续往后走p1(p1null)?headB:p1.next;// p2走到末尾就切换到headA否则继续往后走p2(p2null)?headA:p2.next;}// 最终p1和p2要么同时为null无交点要么指向同一个交点returnp1;}}删除单链表倒数第n个节点classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 1. 边界校验n0 直接返回原链表非法输入if(n0||headnull){returnhead;}// 2. 虚拟头节点解决删除头节点的边界问题ListNodedummynewListNode(0);dummy.nexthead;// 3. 快慢指针初始化都指向虚拟头节点ListNodefastdummy;ListNodeslowdummy;// 4. 快指针先往前走n步for(inti0;in;i){// 如果n超过链表长度直接返回原链表if(fast.nextnull){returnhead;}fastfast.next;}// 5. 快慢指针同时走直到快指针到尾节点while(fast.next!null){fastfast.next;slowslow.next;}// 6. 此时slow指向倒数第n个节点的前驱执行删除slow.nextslow.next.next;// 7. 返回虚拟头节点的next避免删除头节点后返回nullreturndummy.next;}}双向循环链表如果需要支持随机访问的话链表没办法做到。如果需要存储的数据元素的个数不确定并且需要经常添加和删除数据的话使用链表比较合适。//时间复杂度决定如果需要存储的数据元素的个数确定并且不需要经常添加和删除数据的话使用数组比较合适。著作权归JavaGuide(javaguide.cn)所有 基于MIT协议 原文链接https://javaguide.cn/cs-basics/data-structure/linear-data-structure.html//双链表定义classDoublyListNode{intval;DoublyListNodenext,prev;DoublyListNode(intx){this.valxthis.prevnull;this.nextnull;}}添加操作如果我们想在现有的结点 prev 之后插入一个新的结点 cur我们可以将此过程分为两个步骤链接 cur 与 prev 和 next其中 next 是 prev 原始的下一个节点用 cur 重新链接 prev 和 next。与单链表类似添加操作的时间和空间复杂度都是 O(1)。//链接 cur 与 prev 和 nextcur.prevprev;cur.nextprev.next;//2.用 cur 重新链接 prev 和 next。prev.next.prevcur;prev.nextcur;作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/fm9td/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。删除操作我们的目标是从双链表中删除结点 6。因此我们将它的前一个结点 23 和下一个结点 15 链接起来cur.prev.nextcur.next;cur.next.prevcur.prev;经典问题反转链表反转一个单链表一种解决方案是按原始顺序迭代结点并将它们逐个移动到列表的头部算法概述让我们看一个例子请记住黑色结点 23 是原始的头结点。首先我们将黑色结点的下一个结点即结点 6移动到列表的头部然后我们将黑色结点的下一个结点即结点 15移动到列表的头部黑色结点的下一个结点现在是空。因此我们停止这一过程并返回新的头结点 15。在该算法中每个结点只移动一次。因此时间复杂度为O(N)其中 N 是链表的长度。我们只使用常量级的额外空间所以空间复杂度为O(1)。作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/fx61e/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。//递归法classSolution{publicListNodereverseList(ListNodehead){// 递归终止条件空节点 或 只有一个节点无需反转if(headnull||head.nextnull){returnhead;// 最后一个节点会成为新头节点}// 递归调用反转当前节点的后续链表ListNodenewHeadreverseList(head.next);// 核心操作让当前节点的下一个节点指向自己head.next.nexthead;// 断开原指向避免形成环head.nextnull;// 返回新头节点始终是最后一个节点3returnnewHead;}}//迭代法publicListNodereverseList(ListNodehead){//新链表ListNodenewHeadnull;while(head!null){//先保存访问的节点的下一个节点保存起来//留着下一步访问的ListNodetemphead.next;//每次访问的原链表节点都会成为新链表的头结点//其实就是把新链表挂到访问的原链表节点的//后面就行了head.nextnewHead;//更新新链表newHeadhead;//重新赋值继续访问headtemp;}//返回新链表returnnewHead;}作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/f58sg/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。移除链表元素//移除链表中数组为val的元素//递归法classSolution{publicListNoderemoveElements(ListNodehead,intval){if(headnull){returnnull;}head.nextremoveElements(head.next,val);returnhead.valval?head.next:head;}}作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/f9izv/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。//迭代法classSolution{publicListNoderemoveElements(ListNodehead,intval){// 虚拟头节点避免单独处理头节点是目标值的情况ListNodedummynewListNode(0);dummy.nexthead;// 当前遍历节点从虚拟头节点开始ListNodecurrdummy;// 遍历链表检查curr的下一个节点while(curr.next!null){// 找到目标值节点跳过它if(curr.next.valval){curr.nextcurr.next.next;}else{// 未找到正常移动指针关键只有不删除时才移动currcurr.next;}}// 虚拟头节点的next就是新的头节点处理了原头节点被删除的情况returndummy.next;}}奇偶链表给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别分组保持它们原有的相对顺序然后把偶数索引节点分组连接到奇数索引节点分组之后返回重新排序的链表。第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。示例 1:输入: head [1,2,3,4,5]输出: [1,3,5,2,4]示例 2:输入: head [2,1,3,5,6,4,7]输出: [2,3,6,7,1,5,4]作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/fe0kj/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。//建议画图理解classSolution{publicListNodeoddEvenList(ListNodehead){// 边界条件空链表或只有一个节点直接返回if(headnull||head.nextnull){returnhead;}// 定义指针odd指向奇数节点头even指向偶数节点头evenHead保存偶数节点起点ListNodeoddhead;// 奇数节点遍历指针初始在第1位ListNodeevenhead.next;// 偶数节点遍历指针初始在第2位ListNodeevenHeadeven;// 保存偶数节点的头最后拼接用// 循环条件偶数节点不为空且偶数节点的下一个奇数节点不为空while(even!nulleven.next!null){// 奇数节点指向后一个奇数节点跳过偶数节点odd.nexteven.next;// 奇数指针后移oddodd.next;// 偶数节点指向后一个偶数节点跳过奇数节点even.nextodd.next;// 偶数指针后移eveneven.next;}// 将偶数节点链表接在奇数节点链表的尾部odd.nextevenHead;returnhead;}}回文链表反转后半部分链表这题是让判断链表是否是回文链表所谓的回文链表就是以链表中间为中心点两边对称。我们常见的有判断一个字符串是否是回文字符串这个比较简单可以使用两个指针一个最左边一个最右边两个指针同时往中间靠判断所指的字符是否相等。但这题判断的是链表因为这里是单向链表只能从前往后访问不能从后往前访问所以使用判断字符串的那种方式是行不通的。但我们可以通过找到链表的中间节点然后把链表后半部分反转关于链表的反转可以看下432剑指 Offer-反转链表的3种方式最后再用后半部分反转的链表和前半部分一个个比较即可。这里以示例2为例画个图看一下。作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/fov6t/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。publicbooleanisPalindrome(ListNodehead){ListNodefasthead,slowhead;//通过快慢指针找到中点while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}//如果fast不为空说明链表的长度是奇数个if(fast!null){slowslow.next;}//反转后半部分链表slowreverse(slow);fasthead;while(slow!null){//然后比较判断节点值是否相等if(fast.val!slow.val)returnfalse;fastfast.next;slowslow.next;}returntrue;}//反转链表publicListNodereverse(ListNodehead){ListNodeprevnull;while(head!null){ListNodenexthead.next;head.nextprev;prevhead;headnext;}returnprev;}作者LeetCode链接https://leetcode.cn/leetbook/read/linked-list/fov6t/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。