note/algorithm/5、单链表.md

#### 单链表反转

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

```Java
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

```Java
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

```Java
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公式预估递归的时间复杂度，要求子问题数据规模一样。

小和问题