Erlo

iOS常用算法之单链表查找倒数第n个节点(图解)

时间:2019-07-18 11:03   阅读:111次   来源:博客园页面报错

点赞

  拿到题目, 首先要先了解链表数据结构, 如下图:

    

 

  常规思路: 利用数组, 遍历整个单链表, 将每个节点装入数组中, 最终拿到数组根据索引(数组长度-1-n)就得到了倒数第n个元素.

  简单思路:

    假设总长度为n, 

    倒数第k个对应正数第n-k-1,

    那么第一个指针移动k-1次, 第二个指针保持在head不动;

    第一个指针移动到尾部, 共移动n-k-1次, 那么第二个指针同步移动同样次数, 刚好指向第k个节点.

图解验算:

  

  

 

下一篇:iOS常用算法之两个有序数组合并, 要求时间复杂度为0(...

评论留言

还没有评论留言,赶紧来抢楼吧~~

Erlo大厅()

* 这里是“吐槽厅”,所有人可看,只保留当天信息。

  • Erlo.vip2019-08-19 05:48:29Hello、欢迎使用吐槽厅,这里是个吐槽的地方。
  • 首页 笔记分享 案例展示 ERLO 搜索
    鼠标试试
    返回顶部