题目一：实现缓存替换LFS算法。
    解法： 链表桶。

    image.png

    二、责任链 设计模式。

    常规题目：
    一、
    image.png
    解法： 记得是三种方法。
    tips：链表牵扯到换头的问题，要加返回值，如果没有，void就可以。
    题目二：
    image.png
    解法： 谁小谁移动
    image.png

    image.png
    tips：链表在面试中就是考你的coding
    题目三、快慢指针。
    快慢指针定制，谁先走几步。
    image.png
    题目四、长度对比
    题目五、有环情况。
    题目六、image.png
    image.png
    解法1 ： 笔试的时候用stack来保存，然后逆序弹出。
    解法2: 如果省一半空间的话，快慢指针，找到一半，放到栈中。折过来了。
    image.png
    解法3：
    image.png
    step1: 快慢指针，
    step2： 后一半逆序
    step3: 在逆序变成原样。

    1. public class T11_LinkdedList_Palindrome {
    2.     public static void main(String[] args) {
    3.         Node node1 = new Node(1);
    4.         Node node2 = new Node (2);
    5.         Node node3 = new Node (3);
    6.         Node node4 = new Node (2);
    7.         Node node5 = new Node (1);
    9.         node1.right = node2;
    10.         node2.right = node3;
    11.         node3.right = node4;
    12.         node4.right = node5;
    13.         System.out.println(process(node1));
    15.     }
    16.     public static class Node {
    17.         int value ;
    18.         Node left;
    19.         Node right;
    21.         public Node(int value) {
    22.             this.value = value;
    23.         }
    24.     }
    25.     public static boolean process(Node head){
    26.         if(head == null || head.right == null) return true;
    27.         Node slow = head;
    28.         Node fast = head;
    29.         while(fast != null && fast.right != null){
    30.             slow = slow.right;
    31.             fast = fast.right.right;
    32.         }
    34.         /**slow停在了中间位置
    35.          * 做逆序操作*/
    36.         Node tail = reverse(slow);
    38.         /**现在cur就是尾部节点*/
    39.         Node cur = tail ;
    40.         boolean res = true;
    41.         while(cur != null){
    42.             if(head.value != cur.value){
    43.                 res = false;
    44.                 break;
    45.             }
    46.             else {
    47.                 cur = cur.right;
    48.                 head = head.right;
    49.             }
    50.         }
    51.         /**完成之后再逆序回来*/
    52.         reverse(tail);
    53.         return res;
    55.     }
    56.     public static Node reverse(Node head){
    57.         Node pre = null;
    58.         Node cur = head;
    59.         Node next = cur.right;
    60.         while(next!=null){
    61.             cur.right = pre;
    62.             pre = cur;
    63.             cur = next;
    64.             next = next.right;
    65.         }
    66.         cur.right = pre;
    67.         return cur;
    68.     }
    69. }

    左程云版本：
    image.png
    image.png
    题目七：
    image.png
    笔试：
    将每个数收集到数组中，数组上partition，荷兰国旗问题，然后再用node穿起来。
    image.png
    面试：
    就是头为双指针简单应用
    image.png
    时间复杂度O（N），空间复杂度O（1）
    复杂的是头尾为空的判断。链表题目烦的就是边界的讨论。
    image.png
    image.png
    题目八：
    image.png
    笔试：
    1、hashmap将新内存地址对应关系保存起来。
    image.png
    image.png
    面试：
    1、对于任意一个节点，新节点紧随其后，然后串成一条链表，这样新旧就是关系 ，rand指针很好变换了就。
    麻烦的是指针变换代码细节。
    image.png
    image.png
    指针的变换真tm恶习啊，一不留神就少了。

    /**
 * @author 张伟-算法
 * @version 1.0
 * @date 2021/9/9 11:52 下午
 */
public class T12_LinkedList_Copy {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1. next = node2;
        node2.next = node3;
        node1.rand = node3;
        node3.rand = node2;
        node2.rand = null;
        Node copy = process(node1);
    }
    public static Node  process(Node head){
        if(head == null )return null ;
        Node cur = head;
        while(cur !=null){
            Node nodeNew = new Node(cur.value);
            Node next = cur.next;
            cur.next = nodeNew;
            nodeNew.next = next;
            cur = next;
        }
        cur = head;
        while(cur!= null){
            Node copy = cur.next;
            if(cur.rand !=null ) {
                copy.rand = cur.rand.next;
            }
            cur = cur.next.next;
        }

        /**分裂两个链表*/
        cur = head;
        Node head2 = head.next;
        Node cur2 = cur.next;
        while(cur2.next!= null){
            cur.next = cur2.next;
            cur = cur2.next;
            cur2.next = cur.next;
            cur2 = cur2.next;
        }
        return head2;
    }
    public static class Node {
        int value ;
        Node next;
        Node rand;

        public Node(int value) {
            this.value = value;
        }
    }
}

    左程云的：
    image.png

    题目九：单链表相交问题：
    单链表最难的题目了算是
    image.png
    tips：
    1、相交指的是公用节点，跟value无关（第一道题让你求公共部分只是加单判断value是否相等）
    2、有环还可以通过算法求出来第一个入环的节点。
    3、一个链表如果有环，则从如环节点处开始，后序节点都形成环，不会跳出，因为单链表。

    拆分：如何找到入环的节点，
    解法1 ： 用hashMap记录沿途的节点，如果已经在了，这个节点就是入环节点，如果不在，加入到hashMap中。
    解法2: 利用快慢指针，实现空间复杂度O（1）
    image.pngimage.png
    image.pngimage.png
    先用快慢指针过一遍，当两个相遇的时候，将快指针移动到开头，然后两者一步一步走，最终会在入环节点处相遇。
    image.png
    tips： 为什么n1 和 n2 初始化成走一步之后的结果，因为蓝色while 的条件是判断n1 是否 等于 n2；
    回到相交问题：给两个链表的头节点 head1 和 head2；
    image.png
    第一种情况，如果两者都没有环：
    image.png
    step1 ； 遍历第一个链表，求出最后一个节点，并求出长度
    step2: 遍历低第二个链表，求出最后一个节点，求出长度
    step3: 先判断end1 和 end2 是否相等，如果不等，就没有公共区域
    ste4； 否则，较长的链表先走差值步，然后同步移动，一定会在相交节点相遇。

    如果一个有环一个无环，不相交
    如果两个都有环。
    image.png
    step1:判断两个入环节点是否相同，如果相同，将入环节点视为end节点，统计长度，然后套用无环判断相交部分的算法啊（上面）。
    image.png
    image.png
    step1: 转一圈，先看两个入环节点是否有通路，如果没有通路，就没有相交
    step2: 否则，去掉环的长度，利用无欢的
    主函数调用
    image.png
    时间复杂度 O（N）