链表介绍

关于链表相关的算法，其核心就是一个 遍历，遍历链表的所有节点。在遍历的过程中根据题意适当做一些特定的处理。而在遍历链表所有节点时也可以使用递归，无论是前序遍历还是后序遍历。除此之外，你还需要思考以下几个问题：链表的边界处理、针对链表节点的删除和插入处理

链表的边界处理

1. 如果链表为空时，代码是否能正常工作？
2. 如果链表只包含一个结点时，代码是否能正常工作？
3. 如果链表只包含两个结点时，代码是否能正常工作？
4. 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

针对链表节点的删除和插入处理

1. 删除
   1. 删除的是头节点
   2. 删除的是非头节
2. 插入
   1. 插入的位置为头节点
   2. 插入的位置为非头节点

除此之外，链表相关的思想使用最多的就是双指针（快慢指针、伪头指针等）思想

当在题目中碰到 删除 节点操作时一般会使用 伪头指针 进行代码逻辑的统一，因为对于头节点的删除操作与非头节点的删除操作是不一样的

我们都知道若想删除某个节点，我们需要知道该节点的前一个节点，而对于头节点而言根本就没有前一个节点，于是为了让对头节点的操作和普通节点一样，我们可以构造一个虚拟头节点，让它的 next 指针指向头节点，这样就使得对头节点的删除操作和其他节点一样了

也就是说通过 伪头指针 可以将两种操作（头节点与非头节点操作）的代码逻辑进行统一，其中 伪头指针 也称为 哨兵节点 或虚拟头节点

链表与其它数据结构的联系

链表相关相关题目还经常利用栈（后进先出）这种数据结构进行解答

链表的遍历框架

function dfs(list){
  // 获取链表的头节点指针
  let p = list;

  while(condition){ // 一般情况 condition 都是 p !== null
    // handle 代码

    // 更新头节点指针
    p = p.next;

    // handle 代码

  }
  // 遍历完链表之后的 handle 代码
  
}