什么是LRU算法 Least Recently Used，最近最少使用，当数据超过容量时，淘汰最近最少使用的一个然后再进行添加。 用单链表来进行实现： 维护一个链表，从头插入数据。当新数据插入时将新数据作为头部，指向旧的头结点。 向一个单链表插入数据，首先遍历这个链表，查看数据是否已经存在于链表中。如果存在，则删除原有数据，将新数据插入到头结点。 如果不存在，先看是否已经到达容量，如果没有到达容量则插入到头结点。如果到达容量则删除尾部节点，再进行插入。 在这个过程中，将最近使用过的又重新插入到了头部，在链表尾部的就是最近最少使用的一项，所以从尾部删除。

题目来源 今天做了个题： 将一个链表里的数据组装树形结构，链表里的数据已经满足树形结构要求 这道题描述的很简单，但是有很多种情况。他只说了链表数据满足树形结构要求，并没有说明数据到底是什么样的，也就是题目参数具有多样性，这样其实我们给出一种解决方案就可以。而且也只要求将链表转换为树，并没有说是什么树。所以这道题说难也难，说简单也简单。 解题思路 最近也将平衡二叉树的原理看了一下，正好借着这道题将代码手写一下。 我写了一个平衡二叉树的插入方法。我们不管链表里面的数据是如何排序的，我们只要调用树的插入方法即可。在插入方法内部实现树的平衡。 所以我们这道题也就转换成了手写平衡二叉树的插入过程。