双指针-链表 ​

框架思维 ​

void traverse(TreeNode root) {
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

双指针-链表 ​

双指针算法的优化核心思想如下：

当其中一个指针向后移动时，在希望得到答案的情况下，另一个指针只能向着一个方向移动。 当一个指针i向后移动时，另一个指针j不可能向前移动，即j只能不动或者向后移动。 双指针算法的模板一般是使用两个指针i和j，通过while循环，通过判断条件来移动指针i或j，直到满足某种条件。

合并两个有序链表 ​

利用双指针在两个链表中定位较小值，将较小节点接在虚拟链表后，相应指针右移一位，最后将非空的指针接到虚拟链表后。

虚拟链表指头结点是自己新建的虚拟头结点

单链表分解 ​

声明两个虚拟头结点，一个保存大于选定值的，一个小于，遍历给定链表，判断与选定值的大小，从而接入哪一个链表

合并 k 个有序链表 ​

和合并两个有序链表思路差不多,定义k个指针，找到较小值接入，然后右移，不过要使用小顶堆优化找到较小值这一步

单链表的倒数第 k 个节点 ​

准备两个指针，slow指向头节点，fast指向头节点右移k位的节点，同时向右移动，当fast为null的时候，slow即指向倒数第 k 个节点；

单链表的中点 ​

和单链表的倒数第 k 个节点思路差不多,不过fast指针一次移动2位

判断链表是否包含环 ​

定义指针slow，fast，slow++，fast+=2，如果有环，fast肯定会以两倍的路程和slow指针重合

找到环的起点 ​

使fast指向头结点,slow指向相遇点,slow和fast同时移动(++),再次相遇时就是环的起点

相遇点即判断链表是否包含环重合处

两个链表是否相交 ​

p1和p2同时开始循环比较，当p1==null时，使p1=p2再继续遍历比较，p2同理，这样就可以防止交点错位。