note/algorithm/5、单链表.md

单链表反转

使用while循环，保存next节点，设置当前节点的next，保存pre，移动head，最后返回pre

private static Node reverseLinkedList(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head.getNext();
        head.setNext(pre);
        pre = head;
        head = next;
    }
    return pre;
}

双链表反转

使用while循环，保存next节点，设置当前节点的last和pre，保存pre，移动head，最后返回pre

private static Node reverDoubleLinkedList(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head.getLast();
        head.setLast(pre);
        head.setPre(next);
        pre = head;
        head = next;
    }
    return pre;
}

把给定值都删除

单链表实现队列和栈 双链表实现队列和栈 数组实现队列和栈

使用双链表实现双端队列

单链表和双链表的新增、删除，主要注意处理好前驱和后继指针，必要的时候添加中间变量保存。双链表注意处理头尾重合、为空的边界条件。

K个节点的组内逆序调整 LeetCode25

两个链表相加 LeetCode2、LeetCode445

根据链表长度分三段处理，第一段处理短链表，第二段处理长链表多出的部分，第三段处理长链表最后的进位

合并两个有序链表 LeetCode21

位图

位图的功能 保存已知最大值的集合 位图的好处 极大的节省空间 位图的实现 java.util.BitSet

public class BitMap {
    private long[] bits;

    public BitMap(int max) {
        bits = new long[(max + 64) >> 6];
    }

    // 给定数字除以64的结果result，模64的结果mod分开保存，bits[result]位置的mod位设置为1
    public void add(int num){
        // num&63等于num%64
        bits[num >> 6] |= (1L << (num & 63));
    }

    public void delete(int num){
        bits[num >> 6] &= ~(1L << (num & 63));
    }

    public boolean contains(int num){
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }
}

位运算实现加减乘除 LeetCode29

加法add a^b结果为无进位相加，(a&b)<<1是进位信息，递归到进位信息为0，注意中间变量。 减法delete add(a,add(~b,1))，取反加1后为负数。 乘法 a左移b的每一位进制的位数相加。 除法 先取绝对值，a右移到刚好大于等于b，拿到一个商，最后所有商相加，补上符号。对系统最小值特殊处理。

只用栈结构实现队列结构 只用队列结构实现栈结构 图的宽度优先搜索，使用队列实现，图的深度优先搜索，实现栈实现 栈和队列互换后可以实现 图的宽度优先搜索，使用栈实现，图的深度优先搜索，实现队列实现 不考虑时间复杂度

任何地柜都可以改成非递归方式实现。将系统压栈改为自定义实现，则可以避免递归。

master公式预估递归的时间复杂度，要求子问题数据规模一样。

小和问题