list


链表

概况

链表存储空间不一定连续,是临时分配的,所以不能像数组一样用索引提取元素。

大量链表问题可以使用额外数据结构简化。但是最优解一般不使用额外数据结构。

解题要点

  1. 单向/双向?有环/无环?
  2. 翻转链表、交换两个节点是基础
  3. 头节点有可能发生变动的,考虑创建dummy head
  4. 考虑新开一个链表
  5. 快慢指针
  6. 发生指针变动的可能需要分情况讨论
  7. 把需要改变的节点存起来
  8. 链表调整函数的返回值类型,一般是节点类型
  9. 先画图理清思路
  10. 边界条件:头尾节点、空节点

Author: csy99
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source csy99 !
评论
 Previous
greedy greedy
贪心算法 排序!如果是内置数据结构,直接使用自定义排序。排序之后考虑能否使用binary search。 Arrays.sort(arr, new Comparator<int[]>() { public int compa
2020-07-21
Next 
graph graph
图 Graph 图形题不一定需要建图 如果需要建图,考虑边是否具有方向 考虑节点到本身是否有边 建图方式 邻接矩阵 Adjacency matrix space: O(|V|^2) search: O(1) 邻接表 Adj
2020-07-21
  TOC