力扣加加 | 奇幻物语

前言：努力做西湖区最好的算法题解。分为算法专题、91天学算法、精选题解、高频考题（简单-中等-困难）

算法专题

数据结构

线性结构：使用连续内存，序列。利于查询，不利于插入删除
非线性结构：使用间断内存，通过地址指针连接,链表。运行时动态生成

队列、栈都是受限序列。非线性结构是为了高效兼顾静态操作和动态操作，如树堆。
堆是一种优先队列，二叉查找树（查找快），AVL平衡树优化深度的BST，及后面的红黑树。

链表

链表基本操作,画图理解：注意头尾指针情况
插入节点：
1.temp = 待插位置前驱节点.next
2.待插位置前驱节点.next = 待插指针
3.待插指针.next = temp

删除节点：
1.待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next

遍历：
cur = head
while(cur!=nullptr){
print(cur)
cur = cur.next
}

前序遍历递归伪代码

dfs(cur){
  if cur == nullptr
    return
  print(cur.val)
  return dfs(cur.next)
}

一个原则：画图

两个考点：

1.指针修改
比如链表反转，数组直接遍历两两交换

void reverse(head, tail)
{
  cur = head
  pre = nullptr
  while(cur!=tail)
  {
    next = cur->next
    cur->next = pre
    pre = cur
    cur = next
  }
  return tail
}

2.链表拼接
容易穿来穿去。
链表的价值：不必要求物理内存连续性，对插入和删除友好。

三个注意：覆盖90%错误

出现了环，造成死循环
分不清边界，造成边界条件出错
搞不懂递归做法

关于链表环：

题目链表可能有环，判断是否有，以及位置（快慢指针）
本来没环，被你操作出现环（先画图，看操作；仅仅画出一个子结构即可）

关于边界：

如果题目的头节点可能移除，考虑使用虚拟节点，使头节点变成中间节点
题目返回不是原本的头节点，而是尾节点或者中间节点，要注意指针变化

前后序

前序：先处理节点，再左右
中序：先左，再处理，再右
后序：先左右，最后处理节点

由于链表天生具有递归性，可以引入递归思维。

如果前序遍历，可以想象前面链表处理好了，这种情况下处理当前；如果后序，则想象后面处理好了，这种情况下处理当前。

四个技巧

虚拟头作用：

头节点变成中间节点，简化判断
在合适时候断开，返回链表中间节点

快慢指针：

一个先走，一个后走
一个快走，一个慢走

穿针引线：先穿再引，即记录后续改动的，再变更之前的