知识点

基本知识点

链表的顺序表示及其基本操作实现
单链表表示及其基本操作实现
双链表…实现
循环链表…实现

框架：

链表遍历

// 迭代版
function traverse_tpl(head) {
    // for循环
    for (let p=head;p!=null;p=p.next) {
        // 访问p.data
    }
    // or while
    let p = head;
    while(p!=null) {
        // 访问p.data
        p = p.next;
    }
}
// 递归版
function traverse_tpl(head) {
    if (!head) return;
    // 访问p.data;
    traverse_tpl(head.next);
}

技巧类知识点：

快慢指针

**
语雀内容

递归处理链表问题

语雀内容

经典题

141、判断链表是否有环 -> 求链表中环的起始位置
- hash判重思路
- 借鉴循环链表思路，每遍历一个节点将其指向head以此作为省空间的标记方法
- 快慢指针法
142、求链表中环的起始位置
- 快慢指针，同时需要数学推理，有个求解转换的过程
19、删除链表的倒数第N个节点
- 利用快慢指针先后走形成的路程差
876、链表的中间结点 -> 合并两个有序链表 -> 链表的归并排序
- 利用快慢指针的速率差形成的路程差
160、相交链表-两个单链表的公共节点
- 问题转换为长链表遍历指针先走len1-len2的问题，即快慢指针先后走形成的路程差问题
21、合并两个有序链表 -> 链表的归并排序、合并k个有序链表(hard) + 设计推特
- 同两个有序数组合并思路一致
- 考虑迭代和递归两种实现
148、排序链表(nlogn)-链表的归并排序
- 求链表中间结点 + 合并有序链表 = 链表归并排序的核心
147、链表的插入排序 -> 引申：有序数组去重（借鉴插入排序思想）
- 遍历指针p（新来元素）
- 已排序元素的遍历指针prev，遍历时与p比较，直至在已排序元素里找到新来元素的插入位置即prev遍历后的更新值
- 在prev 与 prev.next之间插入新来元素p（链表的插入）
- 更新遍历指针p，p指向下一个新来元素
206、反转链表 -> 每k个一组反转链表
- 头插法
- 循环链表借鉴
  - 优化1：顺向遍历修改指向
  - 优化2：反向遍历修改指向（递归）
234、回文链表
- 额外空间法：数组+遍历，双指针遍历
- 递归法：本质是栈+双指针遍历
- O(1)空间法：快慢指针确定中间节点，反转右半链表
- O(1)空间法：构造成双向链表
两数相加逆序版、两数相加顺序版
- 注意两个case: 1.链表一长一短；2.在原链长基础上需要进位1 如 5+5=10的情况
- 逆序：从左到右遍历，即是低位到高位
- 顺序: 由于遍历顺序与低高位顺序相反，所以需要辅助空间 or 链表反转多次

挑战类：

25、每k个一组反转链表 (<— 反转链表的进阶
23、合并k个有序链表(hard) ( 合并2个有序链表的进阶
355、设计推特（合并有序链表 + oop 的设计结合）
- 设计 Twitter：合并 k 个有序链表和面向对象设计

专文解析：

思维总结

做标记的不同姿势、从快慢指针的由来理解其设计、链表的递归遍历、反转链表的应用

做标记：
1、hash存储，可以区分出每个元素的不同
2、利用某个独一无二的特性
比如给每个元素添加marked标记
比如由于单链表里没有结点会指向头结点，所以利用这一特性给遍历过的结点指向头结点，如果下次再遇到指向头结点的结点，证明之前遇到过这个结点

快慢指针：
由于链表无法从一开始就知道链尾，类似for循环里i < list.length的条件来作为遍历终止
所以当我们需要找到一个链表里的节点时，我们需要快指针走在前面，提前探究到终止
比如，快慢指针确定中间结点，就是利用快慢指针的速率差下的行程差，快指针走到前面探究遍历终点
比如，求倒数第n个节点，快指针先走n步，然后快慢指针同步，当快指针到达终点时，慢指针正好在倒数第n步

链表的递归遍历：
从二叉树的遍历代码理解，前序后序中序代码输出值的位置。从而理解递归函数的思维过程
比如在递归函数调用之前的是递归过程做的事，递归函数之后的，是回溯过程做的事
理解这个过程的一个典型例子：
链表的归并排序
1、分治：递归函数调用之前
2、合并：递归函数调用之后

反转链表：
这个是一个难点，同时也是一个很有用的知识点
code思路：way1、遍历的时候转向；way2、移动结点法 way3、头插法 way4、利用双向链表
一般way1方法比较多地应用在需要链表反转的地方

应用：<br />回文链表

代码模板总结

链表遍历、链表插入、反转链表、合并两个有序链表

链表遍历

# 链表遍历
function traverse2(list){
    // 跳过无意义的头结点
    let p = list.head.next;
    while(p!=null) {
        console.log(p.data);
        p = p.next;
    }
}

function traverse3(list){
    traversecall(list.head.next);
    function traversecall(head){
        if (head==null) return;
        console.log(head.data); // ；链表的前序
        traversecall(head.next);
        console.log(head.data); // ；链表的后序
    }
}

链表结点插入

# 找到新结点预插入位置的前一个结点 prev
let p = new Node(x);
p.next  = prev.next;
prev.next = p;

反转链表

# 顺向改变链接法
let prev = null;
while (head && head.next) {
  // main code
  let next_temp = head.next;
  head.next = prev;
  prev = head;
  head = next_temp;        
}
head.next = prev;
=== 等价于 ===
let prev = null;
while (head ) {
    // main code
}
// head.next = prev;

# 反向遍历法（递归回溯过程改变指向）
function reverseList2(head){
    // 链尾
    if(head==null||head.next ==null){
        return head;
    }
    // 返回新链表的头节点 即原链尾
    let newhead = reverseList(head.next);
    // 此时的head是倒数第二个节点 (当第一次回溯的时候)
    head.next.next = head;
    head.next = null;// 断开原链接 不然要环
    return newhead;
}

遍历两个链表，一长一短的情况（应用场景：归并排序、两数相加）

合并两个有序链表	两数相加

业界应用

如何实现LRU缓存淘汰算法

🤔数据结构与算法

链表总结

知识点

基本知识点

链表遍历

快慢指针

递归处理链表问题

经典题

思维总结

代码模板总结

业界应用