LeetCode 138. Copy List with Random Pointer

思路 《剑指Offer》#26 基本步骤是: 在每个节点后面,拷贝一个相同的节点:A->A’->B->B’… 拷贝随机节点,即A’->random是A->random->next 分离拷贝后的链表 代码 (脑抽了一下,break和continue打错,看了半天)

 

LeetCode 146. LRU Cache

思路 双向链表+哈希表实现,要明白STL里的<map>是红黑树实现的,亲测速度不够,要用真.哈希表:<unordered_map> 可能有人要问,为啥不用单向链表?我的理解是为了删除元素的时候不用从头搜索。 当然,针对这道题是可以用单向链表的,即“删除”最无用节点的时候,对链表不作处理,而只是从哈希表里把值删掉。反正在搜索的时候也是直接查的哈希表。副作用是这个链表会越来越长。 另外,不想自己实现双向链表的话,可以用<list> 代码