linkedList

1 链表

插入的时候，单链表/双链表(先接后面)
往后移，前面的先移动，往前移动，后面的先移动。

与数组不同，我们无法在常量时间内访问单链表中的随机元素。
如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。
我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。
插入和删除操作，将了解到链表的好处。

1. 在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

2. 删除结点的时间复杂度将是 O(N)。空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

2 链表中的双指针

2.1 循环链表

给定一个链表，判断链表中是否有环

在链表中使用两个速度不同的指针时会遇到的情况:

如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少？
一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

方法2，哈希表

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) &#123;
        if (nodesSeen.contains(head)) &#123;
            return true;
        &#125; else &#123;
            nodesSeen.add(head);
        &#125;
        head = head.next;
    &#125;
    return false;
&#125;

2.2 循环链表2

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

1. 快指针1次走2步，慢指针1次走1步。所以快指针总是走了慢指针两倍的路。
2. 回顾一下阶段1的过程，设头节点到入环点的路途为 n, 那么慢指针走了入环路途的一半（n/2）时，快指针就到达入环点了(走完n了)。
3. 慢指针再继续走完剩下的一般入环路途（剩下的n/2），到达入环点时，快指针已经在环内又走了一个 n 那么远的路了。
4. 为了方便理解，这里先讨论环很大，大于n的情况（其他情况后文补充）。此时，慢指针正处于入环点，快指针距离入环点的距离为n。环内路，可以用此时快指针的位置分割为两段，前面的 n 部分，和后面的 b 部分。
5. 此时开始继续快慢指针跑圈，因为已经在环内了，他们其实就是在一条nbnbnbnbnbnbnb（无尽nb路）上跑步。
6. 慢指针从入环处开始跑b步，距离入环处就剩下了n。此时，快指针则是从距离入环处n步远的位置开始跑了2b步，距离入环处也是剩下了n。他们相遇了，并且距离入环处的距离就是n，n就是头节点到入环点的距离阿!!! 后面的不用说了吧。

环很小的情况，其实跟环很大是一样的，比如你可以理解为将多个小环的循环铺开，虚拟扩展成一个大环来理解。

假设 节点到入环口长为 L，环长为C
这里简单讨论C>L的情况, 即一个大环（slow在走到入环口处，fast还没有遍历一遍环)

1. slow到达入口处时，fast 在环 L%C 的位置(slow走L，fast走2L)
2. 设 slow 继续行进 t 长 时，两者相遇， 此时有方程: (L%C+2t)%C = t%C
3. 则 有 L%C + 2t = t+ nC —> L%C+2t = t+nC
4. C>L, 取n=1,得 t = C - L%C, 相遇，L%C=L, 即 目前两者处在环 C-L处，再走 L 长便可到达 入环处
   当C<L，即小环时，n的取值较大，即两者绕环次数多一些，结果还是不变。

public ListNode detectCycle(ListNode head) {
    if(head == null)
        return null;

    // 找到相遇点
    ListNode p1 = getIntersect(head);
    ListNode p2 = head;
    if(p1 == null)
        return null;
    // 头节点到入环处的距离 和 相遇点行走到 入环处的距离 相等
    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

3 模板

3.1 解决链表中的双指针

// 判断是否有环
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}

// 寻找链表的 第一次相遇节点
private ListNode getIntersect(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow == fast)
            return slow;
    }
    return null;
}

3.2 列表反转

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

4 要善用哑变量，特别是在删除的时候

删除链表中等于给定值 val 的所有节点。

public ListNode removeElements(ListNode head, int val) {

    // 巧用 哑变量
    /*
        如果头或者前 n 个 都是要删除的变量， 这样操作比较麻烦
         */
    ListNode dummy = new ListNode(-1);
    dummy.next =  head;
    ListNode cur = dummy;

    while(cur.next!=null){
        if(cur.next.val == val){
            cur.next =  cur.next.next;
        }
        else
            cur = cur.next;
    }
    return dummy.next;
}

5 递归的总结

删除链表中等于给定值 val 的所有节点。

class solution {
    public ListNode removeElements(ListNode head, int val) {
        /*
        和19题 有异曲同工之妙

        1. 递归的结束条件时什么【走到最深处】

        2. 子序列去递归【做什么】

        3. 递归的返值是什么【向上返回】
         */

        if( head == null)
            return null;

        head.next = removeElements(head.next, val);

        if(head.val == val)
            return head.next;
        return head;
        //return head->val == val ? head->next : head;
    }
}