个人总结: 选择排序,就是要又一个游标,每次在做比较的同时,纪录最大值,或者最小值的位置,遍历一遍之后,跟外层每次纪录的位置,做位置交换。...为什么叫选择排序呢,估计就是这个原因,每次遍历一遍,选个最大或者最小的出来。算法因此得名。...,不需要中间变量temp tail-- } else { arry[i], arry[head] = arry[head], arry[i...也是 for j = i; j > 0 && arry[j-1] > temp; j-- { //每次都从外层循环的计数器开始,跟一个temp变量比较,大的话,就往前挪一个窝。...arry[j] = arry[j-1] } arry[j] = temp //最后将挪出来的恰当位置给这个temp变量。也就是每次要插入的值。
反转链表(easy) 方法1.头插法: 动画过大,点击查看 思路:准备一个临时节点,然后遍历链表,准备两个指针head和next,每次循环到一个节点的时候,将head.next指向temp.next,并且将...temp.next指向head,head和next向后移一位。...: 遍历链表,准备prev,curr,next三个指针,在遍历的过程中,让当前指针curr.next指向前一个指针prev,然后不断让prev,curr,next向后移动,直到curr为null 复杂度分析...,在最后一层的时候开始两两反转,让当前递归层的head.next指向交换后返回的头节点,然后让反转后的新的头节点指向当前层的head的节点,这样就实现了两两交换,最后返回反转后链表的头节点 复杂的分析:...-1,存在就返回该节点的值,并且将该节点移动到链表的头部 put的时候,查找哈希表中有没有该键值对,如果存在就更新该节点,并且移动到链表的头部,不存在就创建一个节点,加入到哈希表和链表的头部,并且让节点数
,同时向后遍历,当p2为空,则p1为倒数第k个节点 /** * 找到链表中倒数第k个节点(设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点...= temp.next; } } 3.9查询链表的中间节点 这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点...(算法这方面我还是薄弱啊..脑子不够用了…..)写了两天就写了这么点东西… 操作一个链表只需要知道它的头指针就可以做任何操作了 添加数据到链表中 遍历找到尾节点,插入即可(只要while(temp.next...= null),退出循环就会找到尾节点) 遍历链表 从首节点(有效节点)开始,只要不为null,就输出 给定位置插入节点到链表中 将原本由上一个节点的指向交由插入的节点来指向 上一个节点指针域指向想要插入的节点...对链表进行排序 使用冒泡算法对其进行排序 找到链表中倒数第k个节点 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 删除链表重复数据 操作跟冒泡排序差不多
接着看下,如何将结点node添加到结点3所在的位置。首先,将变量prev向后移动一个位置,指向结点3的前一个结点2所在的位置。 ?...然后,慢指针slow每次向前移动一个位置,快指针fast每次向前移动两个位置。这样,如果链表中存在环,快指针就会先进入环,然后追上慢指针。...slow每次向后移动一个位置,而快指针fast是向后移动两个位置呢?...快指针fast每次向后移动两个位置,如果链表中有环,就会先进入环,从而和慢指针slow相遇,但如果fast每次向后移动一个位置,那么它和慢指针slow之间,一直有一个结点距离,即使链表中有环,也不会相遇...但如果是要查找上一个结点,那么最坏时间复杂度就是O(n)了,因为每次都要从头开始遍历查找链表中的每个结点。 为了解决这个问题呢,就有了双向链表。
我们在车厢内时,每次只能从本车厢到下一个车厢或者上一个车厢,如同对链表的遍历操作一样~~~ ?...找到后让指针指向当前要插入的元素 没有找到是, 每次都需要移动指针temp = temp.next; 思路图 ?...将这个节点的next 指向新的节点 */ public void add(Node heroNode){ //因为head节点不能移动, 因此我们需要辅助变量temp来辅助遍历...return; } // 不为空, 则遍历每个节点, 借助辅助变量temp Node temp = head.next; while (true...HeroNode temp = head; // 创建一个布尔变量,表示待插入是否存在 while (true) { if (temp.next
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。说明:不允许修改给定的链表。...解法一 我们看到在这个链表的末尾连接的下一个节点是链表上的随机一个点,形成一个环形链表,创建一个map,遍历这个链表,key是这个链表的节点,每次map进行put时,判断是否存在,如果存在,说明遇到重复的了...说一个新的方法,我们声明两个临时指针变量,one,two,one变量在遍历链表时每次都指向下一个节点,two则指向下一个节点的下一个节点,当one和two相遇时,two就已经走了one的两倍的长度了,此时我们声明一个临时指针变量...temp,从头部开始遍历,每此遍历都指向下一个节点,one同样,当temp和one相遇时,则这个节点就是入环处,这是什么原理呢?...{ if head == nil{ return nil } //两个快慢指针变量 one,two := head,head for two !
链表在内存中存储如下示意图 head头节点的下一个节点地址为150即a1,a1下一个节点地址为110即a2,a2的下一个节点地址是180即a3.......2.当我们创建第一个节点的时候就让头节点的next域指向第一个节点,当然这个节点包含data域和next域,data存放这个节点的数据,next默认为null 3.当我们每次向单链表中添加数据时,都要遍历单链表中的数据...(因为要拿到next为null的节点),当找到这个next为null的节点后,我们让这个节点的next指向新添加的节点,同时新添加的节点的next被置为null 4.这样一直反复就形成了一个链式存储。...; //初始化temp节点 boolean flag = false; //id是否存在的标识 while (true){ //判断temp是否指向了...双向链表实现思路分析 添加 先找到双向链表的最后一个节点(temp) 使temp.next=新添加节点 使新节点的pre指向temp 遍历 遍历与单链表一样,不过双向链表可以向前向后查找 修改 修改与单链表的修改一样
注意:此处有坑 当我们将当前节点【cur】指向上一个节点【pre】的时候,如何将指针向下移动呢?...最后当前节点没有下个节点的时候,就结束遍历,如图所示。 ? 1.1.2 代码分析 按照套路,先初始化节点对象。...= cur) { // 临时变量保存当前节点的下个节点 ListNode temp = cur.next; // 当前节点的next...为了方便,就继续上面节点的遍历。 ? 题目中描述,如果有2个中间节点,返回第二个节点,所以返回节点【4,5,6】也就符合要求了 1.3.2 代码分析 创建链表结构。...1.5.1 题目分析 这道题和上一篇中的题目【删除排序链表中的重复元素】是一样的,简单的做法即利用Set集合保存未重复的节点,再遍历链表判断是否已存在Set集合中。
,根据实际的需求来确定1.单链表单链表(带头结点)逻辑结构示意图如下1.1单链表的创建和遍历添加先创建一个head头节点,作用就是表示单链表的头后面我们每添加一个节点,就直接加入到链表的最后遍历通过一个辅助变量遍历...节点不能动,因此我们需要一个辅助变量temp HeroNode temp = head; //遍历链表.找到最后 while(true){...,因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while(true){ //判断是否到链表最后...("链表为空"); return; } //因为头节点不能动,因此我们需要一个辅助变量来遍历 HeroNode2 temp = head.next...节点不能动,因此我们需要一个辅助变量temp HeroNode2 temp = head; //遍历链表.找到最后 while(true){
i 文字描述: 遍历链表,第一个元素默认是有序的 在遍历过程中 记录, 有序链表 开始位置: 是否固定下来 ?...head是否改变2个方式 在遍历过程中 记录, 结束位置 : 如果有序,怎么办 ? 如果无顺序怎么办? 约束条件是什么?...,也可以不要,每次寻找pre节点时候 判断一下是否null start.next=head; ListNode* end=head; //有序链表结束位置,end也是遍历的迭代器...ListNode* pre=NULL;//辅助变量 ListNode* temp=NULL;//辅助变量 /** 初始状态...* pre = NULL;//插入排序需要插入记录位置,每次都需要重新计算 //从第一个元素开始遍历链表,假设第一个元素是有序的 while(cur) {
= head; //遍历链表 while (true) { //遍历为空就代表找了最后一个节点 //不为空就后移一位继续找...是位于添加位置的前一个节点,否则插入不了 * */ //创建一个临时变量 HeroNode temp = head; //用来标识 英雄是否存在...if (temp.next == null) { break; } //如果temp的下一个no 大于 我们加入的节点,就往...加入节点的No 那么就代表已经存在了节点 else if (temp.next.No == node.No) { //将flag 修改为 true...,向后继续遍历 temp = temp.next; } // 判断 flag的值 if (flag) {
需要把链表遍历完一次,所以它的时间复杂度为 O(n) 注意:不能先把链表反转,再遍历输出,因为这样做会破坏链表节点原来的顺序。...2-2:改进思路 这里需要用到两个节点型的变量:即变量 first 和 second,首先让 first 和 second 都指向第一个节点,然后让 second 节点往后挪 k-1 个位置,此时 first...和 second 就间隔了 k-1 个位置,然后整体向后移动这两个节点,直到 second 节点走到最后一个节点时,此时 first 节点所指向的位置就是倒数第k个节点的位置。...,每遍历到一个节点都把它放到链表的头节点位置 while (tempNode.getNext() !...于是我们就能想到利用栈来解决这个问题:分别把两个链表的节点放入两个栈中,这样两个链表的尾节点就位于两个栈的栈顶,接下来从两个栈的栈顶开始比较,直到找到最后一个相同的节点,就是他们的公共点。
由于单向链表只能从头遍历,那么在做增删改查操作时,必须从头结点开始遍历。特别是在尾节点做追加操作时,需要将所有节点全部遍历一遍。在时间上花费较多。...但是双向链表就不存在这个问题,在对双向链表做追加操作时只需要对头结点的先序节点进行一次遍历就到达了链表的尾部。这样就大大的减少了时间上的开销。...以下是双向链表的结构示意图: 可以看出,每个节点都有两个指针,一个指向前面,一个指向后面。指向前面的叫先序节点,指向后面的叫后继结点。 我们通过这两个指针来访问所有节点,并通过他们来对链表进行操作。...=tp);i++) { head = head->next; } temp->next = head->next; temp->prior = head; head->next-...->next = head; temp->prior = head->prior; head->prior->next = temp; head->prior = temp; } void
然后慢指针一次走一步,快指针一次走两步,这样快指针走完整个链表时,慢指针正好走到链表的中间。 在遍历的过程中,如果快指针的后一个节点为空,就结束遍历,返回慢指针的值。...,结果加一,如果G中不存在这个值,直接将isComponent置位false,将指针向后移动一位,继续遍历。...只要当前指针存在,就一直遍历,直到遍历完整个链表。...首先让快指针fast先走,向后走k个节点,这样快指针和慢指针之间就相差k个节点。之后,两个指针同时向后移动,直到快指针移动到最后一个节点。...初始化一个temp,用来保存这个哑结点,初始值为list,每次交换都交换temp后面的两个节点。 只有当temp节点之后有至少两个节点时,才能接续往后进行交换,否则结束交换。
但是我们都知道递归是到达底层后才会往上回溯,因此我们可以考虑递归遍历链表,因此三段式如下: 终止条件: 递归进入链表尾,即节点为空节点时结束递归。 返回值: 每次返回子问题之后的全部输出。...具体做法: step 1:我们可以顺序遍历链表,将链表的值push到栈中。 step 2:然后再依次弹出栈中的元素,加入到数组中,即可实现链表逆序。...具体做法: step 1:我们可以顺序遍历链表,将链表的值push到栈中。 step 2:然后再依次弹出栈中的元素,加入到数组中,即可实现链表逆序。...举例 解题思路 方法一:迭代 将链表反转,就是将每个表元的指针从向后变成向前,那我们可以遍历原始链表,将遇到的节点一一指针逆向即可。指针怎么逆向?不过就是断掉当前节点向后的指针,改为向前罢了。...step 3:遍历整个链表,每到一个节点,断开当前节点与后面节点的指针,并用临时变量记录后一个节点,然后当前节点指向上一个节点,即可以将指针逆向。
单链表和双链表的区别 (1)单链表查找的方向只能是一个方向,而双链表可以向前或者向后查找 (2)单链表不能自我删除,需要依靠辅助节点,而双链表可以自我删除(单链表删除时,总是要找到辅助节点temp,temp...//添加数据到双链表最后 public void add(HeroNode2 heroNode) { //因为head头节点不能动,所以需要一个辅助变量temp...HeroNode2 temp = head;//将temp指向head //遍历链表,找到链表最后 while (true) { //当temp的域等于空时...)来帮助找到添加的位置 //找到辅助变量,辅助变量temp应该是位于添加位置的前一个节点,否则无法插入 HeroNode2 temp = head; boolean...break; } temp = temp.next;//如果循环没有结束就一直进行遍历 } //根据 flag 来进行判断是否找到了要修改的节点
以下是一些常见问题以及使用双指针技巧解决 合并两个有序链表: 使用两个指针分别指向两个链表的头部,逐一比较节点的值,将较小的节点链接到结果链表中,直至其中一个链表遍历完毕。...链表的分解: 使用快慢指针技巧,快指针每次移动两步,慢指针每次移动一步,直到快指针到达链表尾部。这样可以找到链表的中间节点,从而将链表分解成两部分。...寻找单链表的中点: 同样使用快慢指针技巧,快指针每次移动两步,慢指针每次移动一步,直到快指针到达链表尾部,慢指针即为中点。...判断两个单链表是否相交并找出交点: 分别遍历两个链表,得到它们的长度差,然后让长链表的指针先移动长度差步数,接着两个链表同时遍历,直到找到相同的节点为止。...=null){ pql.add(head); } } //如果队列不为空,取出优先队列的最小值,加入新链表中,再将最小值的下一节点加入优先队列中
链表的所有结点,每扫描一个结点就创造一个s结点并将值赋给s结点然后头插法插入新链表L中,得到的就是逆序的head链表 typedef struct ListNode ListNode; ListNode...) { ListNode*pcur=head;//用来遍历 ListNode*newhead=BuyNode(-1);//创建哨兵结点 ListNode*temp=NULL;//充当临时变量 while...); newhead=NULL; return head; } 思路3:利用不带头链表头插法,扫描head链表的所有结点,每扫描一个结点就头插法插入新链表L中,得到的就是逆序的head链表...=head;//用来记录尾巴,方便后面置NULL; ListNode*temp;//记录遍历的结点 while(pcur) { temp=pcur->next; //头插到head前面...1 ListNode*p2=list2;//利用p2遍历链表2 ListNode*prev=newhead;//prev记录前驱结点 ListNode*temp=NULL;//充当临时变量
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。...示例3: 输入:head = [1], pos = -1 输出:no cycle 解释:链表中没有环。 进阶: 你是否可以不用额外空间解决此题?...它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。...当发现 slow 与 fast 相遇时,我们再使slow变成head,指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。...; temp = head; for(int i=0;i<n;i++){ temp = temp.next; }
领取专属 10元无门槛券
手把手带您无忧上云