极客算法训练笔记(三)，链表详细图解，别再逃避了朋友（小龙飞飞）

缓存引爆链表
链表单链表双向链表循环链表双向循环链表
Linkedhashmap实现LRU缓存，源码解析（JDK1.8）
算法爬楼梯
算法反转链表
算法链表环检测

缓存引爆链表

存储结构

上一篇说的是数组，然后现在来说说链表。链表有个经典应用，就是实现LRU缓存淘汰算法，缓存的作用大家肯定都知道，常见的Redis缓存，CPU缓存，数据库缓存，浏览器缓存，预热缓存等等缓存技术。缓存大小有限，当缓存满了，需要淘汰策略来决定哪些数据出局，常见缓存算法有三种，这里以缓存中数据命中率来评判缓存算法的优劣来看三种淘汰算法：

FIFO（First in, First out），先进先出策略，不管你是谁，排好队一个一个来，这种做法简单粗暴公平，但是显然是没有考虑缓存数据的使用频率问题了，所以这种算法使用不多；
LFU（Least Frequently Used），最近最不频繁使用策略，即最近最少使用到的数据出局，是从时间和数据使用频率来决定的，

实现：LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序；
缺点：需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序，时间消耗较高；

LRU（Least Recently Used），最近最久未使用策略，主要是从时间来进行淘汰，如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小，把这些数据淘汰掉。

实现：不就是需要根据时间来淘汰嘛，最容易想到的就是数组时间戳，但是这样实现不用想也知道效率贼低。因此java 中的 「LinkedHashMap」 源码就是使用这种缓存算法，底层用双向链表（LinkedList）哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），下面我会把这部分源码进行剖析；
应用：现在使用最广泛的分布式缓存系统如Redis，Memchached，容器如LinkedHashMap 就使用了这种缓存算法，

LRU 和LFU 区别：

LRU:活在当下。比如在公司中，一个新员工做出新业绩，马上会得到重用。

LFU:以史为镜。还是比如在公司中，新员工必须做出比老员工累计更多更好的业绩才可以受到老板重视，这样的方式比较尊重“前辈”。

因此，我们可以就知道链表的伟大贡献了，看到了作用我才去学你懂你，这是我一贯的作风，要不然我学你做什么。

链表

上一节说数组的时候，我一直强调要一段连续的空间，链表就不需要，他是通过“指针”将一组零散的内存块串联起来使用，不需要连续只要有空间就够了。所以链表结点除了数据之外，比数组多存储了个“指针”，数组是靠数组下标偏移量（计算出地址偏移位）找数据，链表是靠指针（直接存储地址）找数据。

在操作链表的时候，要格外注意二点：

边界问题，例如插入有头插尾插中间插入，要注意额外的操作；
代码顺序，防止丢失指针

单链表

链表

首先理解两个概念：

头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。
头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。

不管你有没有头结点，头指针始终是有的，代表了链表的基地址，有基地址才能遍历。头指针始终指向第一个结点，有头结点就指向头结点。

「带头结点好处」

方便第一个位置的插入和删除
统一空表和非空表的处理

有头结点可以简化很多边界问题的考虑，将边界问题转化为正常的结点处理。

最后一个是尾结点，尾结点不指向下一个结点，而是指向空地址NULL，代表这个链表结束了。

中间插入

中间插入

注意点：防止指针丢失和内存泄漏

“=”是赋值，习惯性从右往左读，例插入之前是 p->next = q，q 赋值给 p->next。

错误实现：

p->next=x;//将p的next指针指向x结点; x->next=p->next;//将x的结点的next指针指向b结点;

第一步之后p->next = x，p->next指向了x结点，第二步相当于将 x赋值给 x->next，即相当于x->next = x，自己指向自己，显而易见的问题：q 的地址丢失了，从 q 往后的结点都访问不到，链表断成了两截。后面的地址弄丢了，JAVA有垃圾回收机制还好，C这样的语言程序员如果没有手动释放那些结点占的内存，就产生了内存泄漏，同时删除结点的时候如果不把结点的空间释放也会内存泄漏。

正确实现：

x->next=p->next;//将x的结点的next指针指向b结点; p->next=x;//将p的next指针指向x结点;

顺序调换一下，先将q的地址存储好放到x结点，然后x结点再链接到p结点就好了。

这个问题开始重视起来是在大三找实习一家游戏公司总监问到，让我把这个地方再说一遍，我暗地里虎躯一震菊花一紧表面上却稳如泰山，最后用温柔的微笑让他如沐春风从而化解了这个尴尬，马上改口。

头插入

头插法

x->next=head->next;//将x的结点的next指针指向b结点; head->next=x;//将p的next指针指向x结点;

可知有了头结点，头插入代码和中间插入代码是一样的，只不过上一个p结点变成了head 结点。

尾插入

尾插法

x.next=null; tail.next=x;头插法 VS 尾插法

HashMap 源码中，jdk8之前hash冲突时候用的都是头插法，jdk1.8之后用的尾插法，不知道你是否还有印象，主要原因是防止扩容的时候头插法造成链表环化，具体的读者有兴趣看看扩容源码。

头插法：遍历时候得到的数据顺序和插入的时候是相反的，原因是你第一次插进去的数据实际上成为了链表的尾巴；

尾插法：遍历得到的数据和插入的顺序是一致的。

删除结点

删除中间结点

p->next = p->next->next; 一行代码就可以

双向链表

双向链表

单链表的插入、删除操作的时间复杂度已经是O(1)了，为什么还要双向链表呢？优点在哪里。

还是从插入，删除，查找来看，拿删除操作来分析，无非两种情况：

删除给定指针指向的结点
删除结点中值等于xxx的结点

第二种，对于单链表和双链表都需要先进行遍历，直到找到值等于给定值的结点，然后删除；

第一种，区别就来了，我们已经找到了要删除的结点，但是删除某个结点q需要知道其前驱结点，单链表找前驱结点还是需要遍历先找到前驱结点，双链表就可以直接拿到前驱结点；

然后实际应用中，例如容器 HashMap，都是知道指针，第一种操作比较多，删除插入操作就是指针的操作，值都是动态变得不可能告诉你一个值再让你删除，所以这种结构的重要性不言而喻了，插入操作这里不再分析了。

循环链表

循环链表

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。

❝
约瑟夫问题据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自*方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自*，然后再由下一个重新报数，直到所有人都自*身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并*掉第k个人。接着，再越过k-1个人，并*掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
❞

双向循环链表

双向循环链表

LinkedHashMap实现LRU缓存，源码解析（JDK1.8）

/** *Acacheimplementingaleastrecentlyusedpolicy. */ publicclassLRUCache<K,V>implementsCache<K,V>{ privatefinalLinkedHashMap<K,V>cache; publicLRUCache(finalintmaxSize){ cache=newLinkedHashMap<K,V>(16,.75f,true){ @Override protectedbooleanremoveEldestEntry(Map.Entry<K,V>eldest){ returnsize()>maxSize; } }; } 方法伪代码： publicVget(Kkey) publicvoidput(Kkey,Vvalue) publicbooleanremove(Kkey) publiclongsize() }

可以得知 LRUCache 缓存就是使用 LinkedHashMap 结构实现的。

LinkedHashMap结构图

LinkedHashMap 继承了 HashMap（jdk1.8），总的结构还是数据链表红黑树，为了简化思想图里面没有红黑树的，就这样看哦；

publicclassLinkedHashMap<K,V> extendsHashMap<K,V> implementsMap<K,V> { /** *HashMap.NodesubclassfornormalLinkedHashMapentries. */ staticclassEntry<K,V>extendsHashMap.Node<K,V>{ Entry<K,V>before,after; Entry(inthash,Kkey,Vvalue,Node<K,V>next){ super(hash,key,value,next); } } privatestaticfinallongserialVersionUID=3801124242820219131L; //双向链表头结点 transientLinkedHashMap.Entry<K,V>head; //双向链表尾结点 transientLinkedHashMap.Entry<K,V>tail; //如果accessOrder为flase的话，则按插入顺序来遍历，默认fasle /** true基于访问顺序当accessOrder设置为true时，被访问的数据，将会被移到链表的尾部，put使用的也是尾插法；同时get是从尾部开始访问，所以等于越常使用的数据，遍历的时间越短。 **/ finalbooleanaccessOrder;

LRU 初始化启动 true

LRU 缓存初始化的时候，就用了这个 accessOrder，设置为true，从而最近被访问到的数据放到了链表末尾，链表前面的数据是长时间没有使用的，从链表末尾开始访问的话，链表头部开始的长久没有访问的数据就被淘汰掉了，从而实现LRU缓存。

Map的Entry结点内容 staticclassNode<K,V>implementsMap.Entry<K,V>{ finalinthash; finalKkey; Vvalue; Node<K,V>next; Node(inthash,Kkey,Vvalue,Node<K,V>next){ this.hash=hash; this.key=key; this.value=value; this.next=next; } ······· } //LinkedHashMap的Entry，可以看到比Map的结点多了两个指针before,after staticclassEntry<K,V>extendsHashMap.Node<K,V>{ Entry<K,V>before,after; Entry(inthash,Kkey,Vvalue,Node<K,V>next){ super(hash,key,value,next); } }

//生成一个新的结点 Node<K,V>newNode(inthash,Kkey,Vvalue,Node<K,V>e){ LinkedHashMap.Entry<K,V>p= newLinkedHashMap.Entry<K,V>(hash,key,value,e); //结点尾插法放入链表最后 linkNodeLast(p); returnp; } //尾插法，把新结点插入链表末尾 privatevoidlinkNodeLast(LinkedHashMap.Entry<K,V>p){ //尾结点赋值给last指针 LinkedHashMap.Entry<K,V>last=tail; //P结点赋值给尾结点 tail=p; //如果尾部节点为空，说明是空链表，那么插入的就是第一个节点。这个时候新加入的数据赋给头部节点 if(last==null) head=p; //不是空链表，将新结点放到末尾 else{ p.before=last; last.after=p; } }

LinkedHashMap是继承的HashMap，插入删除都是直接用的HashMap的插入删除方法，只不过它重写了三个回调方法，来实现他需要的额外操作，如下：

//在hashmap正常删除一个结点之后进行回调 voidafterNodeRemoval(Node<K,V>e){ /**定义了一个结点p，将传递进来的的e结点赋值给p，把传进来的e结点赋值给p结点，并且定义p的前驱结点b，后继结点a **/ LinkedHashMap.Entry<K,V>p= (LinkedHashMap.Entry<K,V>)e,b=p.before,a=p.after; p.before=p.after=null; //如果前一个结点是null，那么这是个空链表 if(b==null) head=a; else b.after=a; if(a==null) tail=b; else a.before=b; }

//在hashmap正常插入一个结点之后进行回调，插入一个结点可能缓存满了，因此需要移除最久没有使用的结点即第一个结点（前面讲了LRU的调度算法，不明白的可以回头去看） /** //根据evict,也就是前文linkedHashMap构造函数中的accessOrder，来判断是否删除双向链表中最老的元素，这个是实现lru需要用到的。 **/ voidafterNodeInsertion(booleanevict){//possiblyremoveeldest LinkedHashMap.Entry<K,V>first; if(evict&&(first=head)!=null&&removeEldestEntry(first)){ Kkey=first.key; //hashmap的移除结点方法，传key第一个结点过去进行删除 removeNode(hash(key),key,null,false,true); } }

//最常用是hashmap正常putVal之后调用，将新加入的结点移动到链表末尾 voidafterNodeAccess(Node<K,V>e){//movenodetolast LinkedHashMap.Entry<K,V>last; if(accessOrder&&(last=tail)!=e){ //把传进来的e结点赋值给p结点，并且定义p的前驱结点b，后继结点a LinkedHashMap.Entry<K,V>p= (LinkedHashMap.Entry<K,V>)e,b=p.before,a=p.after; p.after=null; if(b==null) head=a; else b.after=a; if(a!=null) a.before=b; else last=b; if(last==null) head=p; else{ p.before=last; last.after=p; } //把p结点赋值给尾结点 tail=p; modCount; } }

afterNodeAccess()方法图解：

afterNodeAccess 方法图解

还是挺复杂的，画了一个多小时这张图。

算法爬楼梯

上一篇的遗留算法：

爬楼梯

超哥说，「解决所有问题的法则」：

找最近重复的子问题；
为什么？因为写程序我们只能写if，else，for，while，recursion（递归）；
计算机是人类发明的，计算机肯定是没有人脑那么强的，它其实就是一个简单的重复式机器那么计算机运行的程序也是同理，它是用重复的东西来解决问题的；
如果我们遇到算法题的时候，就是需要我们用程序去解决的问题，那问题的本身就是可重复的；
无论是算法中的回溯、分治、动态规划、递归等，全部都是在找重复性的原理所以重点都是“找规律”；

分析问题：

刚刚拿到，没有思路，先暴力举例一阶（1种）：1

二阶（2种）：1 1，2

三阶（3种）：1 1 1，2 1，1 2 即二阶的走法 1和一阶的走法 2

四阶（5种）：1 1 1 1，1 2 1，2 1 1，1 1 2，2 2，即三阶的走法 1和二阶的走法 2，共五种

五阶（8种）：1 1 1 1 1，1 2 1，2 1 1，1 1 2 1，2 2 1，1 1 1 2，2 1 2，1 2 2 即四阶的走法 1和三阶的走法 2，共八种

......

思想：例如一共10阶，那么有两种方法，要不就是你走到了第八阶跨2步，或者走到第九阶了跨1步，再也没有别的实现了，因为你一次性只能跨两步或者一步，所以最终次数就是到达第八阶次数到达第九阶的次数，f(10)=f(9) f(8),每一层都是如此情况，即在上一个台阶走2步或者走1步到达终点，可知这其实是个斐波拉契问题。

「实现：」