数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

06 | 链表(上):如何实现LRU缓存淘汰算法?

王争 2018-10-03
今天我们来聊聊“链表(Linked list)”这个数据结构。学习链表有什么用呢?为了回答这个问题,我们先来讨论一个经典的链表应用场景,那就是 LRU 缓存淘汰算法。
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。
这些策略你不用死记,我打个比方你很容易就明白了。假如说,你买了很多本技术书,但有一天你发现,这些书太多了,太占书房空间了,你要做个大扫除,扔掉一些书籍。那这个时候,你会选择扔掉哪些书呢?对应一下,你的选择标准是不是和上面的三种策略神似呢?
好了,回到正题,我们今天的开篇问题就是:如何用链表来实现 LRU 缓存淘汰策略呢? 带着这个问题,我们开始今天的内容吧!

五花八门的链表结构

相比数组,链表是一种稍微复杂一点的数据结构。对于初学者来说,掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构,我们常常将会放到一块儿来比较。所以我们先来看,这两者有什么区别。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(502)

  • Rain 置顶
    Re Ydyhm:

    “数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。” 这里的CPU缓存机制指的是什么?为什么就数组更好了?

    ----

    我没有百度也没有Google。之前开发时遇到过,我斗胆说下。
    CPU在从内存读取数据的时候,会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址,而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中,然后下次访问内存数据的时候就会先从CPU缓存开始查找,如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制,也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。

    对于数组来说,存储空间是连续的,所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。

    大牛请指正哈!

    作者回复: 同学,太爱你了。写的太好了!就喜欢你这样的,减轻了我很多回复留言的工作量。👍

    2018-10-04
    13
    685
  • andavid 置顶
    思考题:

    使用快慢两个指针找到链表中点,慢指针每次前进一步,快指针每次前进两步。在慢指针前进的过程中,同时修改其 next 指针,使得链表前半部分反序。最后比较中点两侧的链表是否相等。

    时间复杂度:O(n)
    空间复杂度:O(1)

    https://github.com/andavid/leetcode-java/blob/master/note/234/README.md

    作者回复: 思路正确,不过空间复杂度计算的不对,应该是O(1),不是O(n)。我们要看额外的内存消耗,不是看链表本身存储需要多少空间。

    2018-10-03
    11
    194
  • Liam 置顶
    1 快慢指针定位中间节点
    2 从中间节点对后半部分逆序
    3 前后半部分比较,判断是否为回文
    4 后半部分逆序复原

    时间复杂度On, 空间复杂度O1
    把LRU和回文都实现了一遍~~

    如果是双向链表,时间效率更高,看了下LinkedList,底层也是用双向链表实现

    作者回复: 回答的很好!👍

    2018-10-03
    98
  • glbfor.gtw 置顶
    1 快慢指针定位中间节点(这里要区分奇偶情况)
    1.1 奇数情况,中点位置不需要矫正
    1.2 偶数情况,使用偶数定位中点策略,要确定是返回上中位数或下中位数
    1.2.1 如果是返回上中位数,后半部分串头取next
    1.2.2 如果是返回下中位数,后半部分串头既是当前节点位置,但前半部分串尾要删除掉当前节点
    2 从中间节点对后半部分逆序,或者将前半部分逆序
    3 一次循环比较,判断是否为回文
    4 恢复现场

    题外话,这种操作有点BT啊?实际运用场景中,也真的直接改变引用值吗?至少在多线程情况,要加N多锁(Read Write都要加锁),这个时间成本就不能简单用时间复杂度来衡量了。如果是用copy 机制,不论是倒置前半段还是后半段,至少有一段是需要n/2个节点副本的空间消耗的,那么空间复杂度就是O(n)??啦~跑题了,跑题了~~

    老师,你给我评价被~ 我比较容易钻牛角尖。。

    作者回复: 👍 回答的非常好

    2018-10-11
    3
    46
  • sky 置顶
    用快慢指针先找到中点,然后把后半段链表reversed,然后一个指针在头部,一个指针再中点,开始逐个比较,时间复杂度是O(n)

    作者回复: 对的!👍

    2018-10-09
    19
  • molybdenum
    看了大家的评论学习到了快慢指针法,看语言描述没太懂,自己用代码写了下才明白。
    大致思路如下
    由于回文串最重要的就是对称,那么最重要的问题就是找到那个中心,用快指针每步两格走,当他到达链表末端的时候,慢指针刚好到达中心,慢指针在过来的这趟路上还做了一件事,他把走过的节点反向了,在中心点再开辟一个新的指针用于往回走,而慢指针继续向前,当慢指针扫完整个链表,就可以判断这是回文串,否则就提前退出,总的来说时间复杂度按慢指针遍历一遍来算是O(n),空间复杂度因为只开辟了3个额外的辅助,所以是o(1)
    2018-10-07
    13
    277
  • 姜威
    五、应用
    1.如何分别用链表和数组实现LRU缓冲淘汰策略?
    1)什么是缓存?
    缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
    2)为什么使用缓存?即缓存的特点
    缓存的大小是有限的,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?就需要用到缓存淘汰策略。
    3)什么是缓存淘汰策略?
    指的是当缓存被用满时清理数据的优先顺序。
    4)有哪些缓存淘汰策略?
    常见的3种包括先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frenquently Used)、最近最少使用策略LRU(Least Recently Used)。
    5)链表实现LRU缓存淘汰策略
    当访问的数据没有存储在缓存的链表中时,直接将数据插入链表表头,时间复杂度为O(1);当访问的数据存在于存储的链表中时,将该数据对应的节点,插入到链表表头,时间复杂度为O(n)。如果缓存被占满,则从链表尾部的数据开始清理,时间复杂度为O(1)。
    6)数组实现LRU缓存淘汰策略
    方式一:首位置保存最新访问数据,末尾位置优先清理
    当访问的数据未存在于缓存的数组中时,直接将数据插入数组第一个元素位置,此时数组所有元素需要向后移动1个位置,时间复杂度为O(n);当访问的数据存在于缓存的数组中时,查找到数据并将其插入数组的第一个位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉末尾的数据,时间复杂度为O(1)。
    方式二:首位置优先清理,末尾位置保存最新访问数据
    当访问的数据未存在于缓存的数组中时,直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1);当访问的数据存在于缓存的数组中时,查找到数据并将其插入当前数组最后一个元素的位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉数组首位置的元素,且剩余数组元素需整体前移一位,时间复杂度为O(n)。(优化:清理的时候可以考虑一次性清理一定数量,从而降低清理次数,提高性能。)
    2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”?(比如 上海自来水来自海上)
    1)前提:字符串以单个字符的形式存储在单链表中。
    2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
    3)将链表中的字符倒序存储一份在另一个链表中。
    4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。
    六、设计思想
    时空替换思想:“用空间换时间” 与 “用时间换空间”
    当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。

    作者回复: 👍

    2018-10-03
    5
    216
  • 姜威
    总结
    一、什么是链表?
    1.和数组一样,链表也是一种线性表。
    2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
    3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。
    二、为什么使用链表?即链表的特点
    1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。
    2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。
    三、常用链表:单链表、循环链表和双向链表
    1.单链表
    1)每个节点只包含一个指针,即后继指针。
    2)单链表有两个特殊的节点,即首节点和尾节点。为什么特殊?用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    3)性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。
    2.循环链表
    1)除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    2)适用于存储有循环特点的数据,比如约瑟夫问题。
    3.双向链表
    1)节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
    2)首节点的前驱指针prev和尾节点的后继指针均指向空地址。
    3)性能特点:
    和单链表相比,存储相同的数据,需要消耗更多的存储空间。
    插入、删除操作比单链表效率更高O(1)级别。以删除操作为例,删除操作分为2种情况:给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况,单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除,时间复杂度为O(n)。对于第二种情况,要进行删除操作必须找到前驱节点,单链表需要从头到尾进行遍历直到p->next = q,时间复杂度为O(n),而双向链表可以直接找到前驱节点,时间复杂度为O(1)。
    对于一个有序链表,双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p,每一次查询时,根据要查找的值与p的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。
    4.双向循环链表:首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。
    四、选择数组还是链表?
    1.插入、删除和随机访问的时间复杂度
    数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
    链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。
    2.数组缺点
    1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
    2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。
    3.链表缺点
    1)内存空间消耗更大,因为需要额外的空间存储指针信息。
    2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。
    4.如何选择?
    数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。
    如果代码对内存的使用非常苛刻,那数组就更适合。

    作者回复: 👍

    2018-10-03
    1
    75
  • _stuView
    双向链表存储,两个指针分别从头节点和尾节点开始遍历,依次比较节点value,判断是否为回文序列
    2018-10-03
    4
    47
  • 徐凯
    通过一个栈 遍历整个链表 然后再从栈中弹出 如果元素都匹配则为回文
    2018-10-03
    6
    35
  • Joshua 兆甲
    习题解答
    1.快进慢进法[两组指针,从头开始,a组一次进一,b组一次进二,b组到终点时,a组位置即为链表中间结点,循环次数为链表除去中间结点后前后两组的长度] 求得单向链表“中间”节点。并计算遍历次数,经过验证,遍历次数为‘’半链表‘’长度
    2.从中间结点开始,以动态步长[每第i次步长是半链表长度-i+1]遍历链表,同时,从头节点开始,以1步长遍历。比较两组对应元素是否相同,相同继续,不同退出,返回不是回文字符串的结论。
    3.返回是回文字符串的结论,退出.
    空间复杂度O(n). 不用连续内存,可以磁盘操作
    时间复杂度度O(n). 主要费时操作遍历

      算了,不够直观,不易别人看懂。还是先把单项链表转存为线性表。
    1.单向遍历,获得对应的线性表Arr,求线性表长度为L
    2.运用线性表可以任意访问的性质,遍历Arr,令下标i从0。比较Arr[i]和Arr[L-i]是否相等 相等继续,不等报告不是回文字符串结论,退出
    3.报告是回文字符串结论,结束。
    空间复杂度O(n)
    时间复杂度O(n)
    看起来一样,这个就需要字符串不太大,有足够的连续内存可以分配,而且,预先不知道链表多长,可能还会遇到扩容问题。
    2018-10-03
    2
    35
  • 雨山
    果然有程序员风格,放假还更新,昨天临睡前就看完了,但是没有评价,总之这个课绝对物有所值。
    2018-10-03
    31
  • 落叶飞逝的恋
    老师,关于解答开篇那边,能不能附加一些代码示例,这样配合代码跟思路讲解,可能更好的理解呢。
    2018-10-03
    28
  • 无崖子🍀
    用数组解决Lru缓存问题:
    维护一个有序的数组,越靠近数组首位置的数据越是最早访问的。
    1.如果这个数据已经存在于数组中,把对应位置的数据删掉,直接把这个数据加到数组的最后一位。时间复杂度为o(n)
    2.如果数据不存在这个数组中,数据还有空间的话,就把数据直接插到最后一位。没有的话,就把第一个数据删掉,然后把数据插入到数组最后一个。这样的时间复杂度为o(n)。

    第一个小伙伴的留言有点问题。判断是否为回文串和奇偶数没关系吧,偶数个字符串也可以是哈,比如abccba。
    2018-10-05
    1
    26
  • JStFs
    LRU:活在当下。比如在公司中,一个新员工做出新业绩,马上会得到重用。

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

    作者回复: 哈哈 形象!

    2018-10-04
    24
  • null
    老师,您回复 JK David 说到:
    空间复杂度计算的不对,应该是O(1),不是O(n)。我们要看额外的内存消耗,不是看链表本身存储需要多少空间。


    在《复杂度分析(上)》提到:
    第 3 行申请了一个大小为 n 的 int 类型数组,所以整段代码的空间复杂度就是 O(n)。


    ----


    疑问一:
    为什么两处计算空间复杂度的方法不一致,回复评论是以额外消耗为准,而文章中是以分配存储的空间为准?


    疑问二:
    《复杂度分析(上)》中介绍空间复杂度没有时间复杂度详细且带例子,看到老师您回复 JK David 以额外消耗为分析对象,就更懵圈了。
    如果说:
    1. 额外消耗常量值内存的空间复杂度是 O(1);
    2. 额外消耗 n 内存的空间复杂度是 O(n);
    那么空间复杂度是 O(n 的平方),如何才能额外消耗 n 的平方空间呀?
    老师能否针对空间复杂度,有一个更详细的说明和举例呢?


    谢谢老师
    2018-10-07
    15
  • Kevin.zhang🌏
    习题解,大部分同学都说到了方法一:半栈法
         1.用快慢两个指针遍历,同时用栈copy慢指针指向的data。
         2.完成后,慢指针指向中间节点,耗时为N/2.
         3.最后用pop栈中的data和慢指针指向的data比较,耗时也是N/2.
              所以时间复杂度为:O(N),空间复杂度因栈额外存储了一半的data,故为O(N/2)

    方法二:全栈法
         1.全部遍历,data压栈,额外空间消耗N
                        2.再次全部遍历取data,同时pop栈取data, 二者比较,时间消耗2N
              所以时间复杂度为O(3N),空间复杂度为O(N)
              该法算法最简单,但复杂度高。可以用栈存储节点指针,而非data来改进。

    方法三:硬干法
         1. 一个指针从头取data,另一个指针遍历到底取data,比较二者
         2.删除尾部节点,重复1.
       时间复杂度高达 O(N^2),空间复杂度却最低O(1)
    2018-11-09
    4
    14
  • Smallfly
    思考题:根据原有单链表回文创建一个逆向的单链表回文,while 循环遍历比较,复杂度为 O(N)。
    2018-10-03
    10
  • 5ispy
    老师好,关于这节的内容有个疑问不太确定。
    因为我看有人用java实现了链表有人也可以用c来实现。是不是数组属于编程语言“自带”的,而链表是 人 用编程语言 “实现”的。
    比如对于java来说,如果项目中用到了链表,我们可以说是用到了某个类,而这个类就是 链表(实现了链表的功能)。
    恳请老师指正!

    作者回复: 你理解的没错

    2018-10-10
    1
    9
  • 六六六
    判断单链表是否是回文,只想到了这种low一些的做法,时间复杂度为O(n^2):
    public static boolean isHuiwen(LinkedList linkedList) {
            Node first = linkedList.getFirst();
            int size = linkedList.getSize();
            Node head = null;
            Node foot = null;
            for (int a = 0; a < size / 2; a++) {
                head = head == null ? first : head.next;
                foot = head;
                for (int i = a; i < size - 1 - a; i++) {
                    foot = foot.next;
                }
                if (!head.getData().equals(foot.getData())) {
                    return false;
                }
            }
            return true;
        }
    2018-10-03
    1
    9
收起评论
99+
返回
顶部