Algorithm Module

• 1. List
• 2. 链表
• 3. List
• 4. 先走几步模块
• 5. 快慢指针半分链表
• 6. 翻转链表迭代&递归
• 7. 链表排序
• 8. 链表 add number
• 9. sort array
• 10. 二叉树前序、中序和后续遍历
• 11. 二叉树层次遍历

• ArrayList随机访问（改查。访问特定索引和修改）效率很高，但插入和删除性能比较低。linkedList反之。
• linkedList实现了Queue接口。

public interface Queue extends Collection {
    boolean offer(E e); // 尾部添加元素 长度有限制并且队列被占满时返回false
    boolean add(E e); // 尾部添加元素，长度有限制并且队列被占满时IllegalStateException

    E peek(); //查看头部元素，空队列时返回null
    E element(); //查看头部元素，空队列时返回NoSuchElementException

    E poll(); //删除头部元素并返回之，空队列时返回null
    E remove(); //删除头部元素并返回之，空队列时返回NoSuchElementException
}

• Java中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口Deque中。linkedList也实现了Deque接口，可用linkeList模拟堆栈。主要方法有
  void push(E e); E pop(); E peek(); 前两方法可能抛出IllegalStateException和NoSuchElementException
• linkedList模仿Deque, 方法如下：
  offer/add(First|Last), peek/get(First|Last), poll/remove(First|Last)
• linkedList 总结：https://www.zhuxiaodong.net/2018/collection-in-java-linkedlist/

private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

linkedList 是一个 List ，但也实现了 Deque 接口，可以作为队列、栈和双端队列使用。实现原理上， linkedList 内部是一个双向链表，并维护了长度、头节点和尾节点，其特性为：
- 按需分配空间，不需要预先分配很多空间。
- 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，复杂度为 O(N/2) 。之所以为 O(N/2)，是因为会首先判断索引位置是否在中间，来决定是头节点进行遍历，还是从尾节点进行遍历。
- 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，复杂度为 O(N)。
- 在两端添加、删除元素的复杂度为 O(1)。
- 在中间插入、删除元素，要先定位，效率比较低，复杂度为 O(N/2)，但修改本身的效率很高，复杂度为 O(1)。
理解了 linkedList 和 ArrayList 的特点，就能比较容易地进行选择了，如果列表长度未知，添加、删除操作比较多，尤其经常从两端进行操作，而按照索引位置访问相对比较少，则 linkedList 是比较理想的选择。

// 单向链表节点定义
class ListNode {
    int val;
    ListNode next;
    ListNode();
    ListNode(int v) {
        this.val = v;
    }
    ListNode(int v, ListNode n) {
        this.val = v;
        this.next = n;
    }
}

// TreeNode节点定义
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

List list = new ArrayList<>();

linkedList stack = new linkedList<>(); // 支持push(), pop(), peak()等
Stack stack = new Stack<>(); // 支持push(), pop(), peak()等

        // 辅助头结点法
        ListNode aux = new ListNode(-1);
        aux.next = head;

        ListNode p = aux; // or from head
        int cnt = 1;
        while (p != null && p.next != null && cnt < m) { // 主要p!=null最好都带着，因为有些时候每次循环不止走一步
            p = p.next;
            cnt++;
        }
        if (cnt != m) {System.out.println("cnt != m，则链表长度不够；否则是能让p走到第m个节点")}

        // 切分前后两半，各自排序，再merge
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) { // 结束时slow卡在中间节点，fast在tail
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode right = slow.next;
        slow.next = null;

    // 迭代：辅助节点aux, 遍历指针p从head向后移动到链表tail.next(即null，while(p != null)方式操作)
    // 发散：迭代或遍历3.5个点：1. 初始的状态，如用几个指针，初始指针位置 2. 终止状态，如终止时指针位置 3. 算法操作Algorithm Operation, 这部分一般先保护现场，使重要的变量不被污染或丢失 3_5. 递进条件，通常是遍历指针的赋值，使循环得以继续走下去，一般在算法操作之后
    public ListNode reverseList1(ListNode head) {
    	// boundary check， validation check
        if (head == null || head.next == null) {
            return head;
        }
        // main logic
        ListNode aux = null, p = head;  // 1. 初始指针位置
        while(p != null) {              // 2. 终止指针位置p==null, 那么在循环中就是not(终止状态) p!=null
            ListNode next = p.next;     // 3. 算法操作，临时变量保护重要的变量，进行算法操作
            p.next = aux;               

            aux = p;                    // 3.5. 递进条件
            p = next;
        }
        return aux;
    }

    // 递归：先用递归到链表末尾tail（用head.next==null做recursion end condition）其实就是翻转后新的头结点, 然后根据从后向前更换next指针。注意需要prev.next=null来解开原来的prev->next的关系。
    // 发散：递归注意点：1. 终止的状态是什么，往往就是最简情况，即边界检查时的条件。递归函数1st Line 2. 初始状态是什么，涉及哪些指针？递归一般用递归方法的传入指针，不用额外构造中间的递归变量。注意，一般通过传入初始递归变量的下一子节点/继节点，来建立前后的的节点关系，方便算法操作。 3. 算法操作 3.5 问题空间缩小/收敛的条件, 其实就是再次调递归函数(传参的问题空间更小),这里和算法操作的先后顺序不一定，可能在前可能在后。一般而言，不污染递归指针的算法操作可前可后(如Tree的前序遍历list.add(root.val)放在最前)，污染的话一般在后(这里链表的翻转，是先递归到底，再返程算法操作，污染了递归变量的)。
    public ListNode reverseList3(ListNode head){
    	// // 1. boundary check。注意，这里也是递归终止状态recursion end condition，终止状态就是链表常规的边界条件。
        if (head == null || head.next == null) {
            return head;
        }


        ListNode reversedNode = reverseList3(head.next); // 2. 初始状态 head指针，3&3.5 算法操作会污染递归变量，置后。通过head.next缩小问题范围，收敛条件
        head.next.next = head; // 算法操作
        head.next = null;      // 算法操作：这一步是为了解开原来的prev->next的关系。
        return reversedNode;
    }

    //  发散：归并和快排，首先需要递归来分而治之，缩小问题空间。具体的算法操作是由具体模块来实现，merge模块合并两个有序的链表，partition模块每次将一个数摆到最终的正确次序上。

    // merge(mergeSort(left), mergeSrot(right))
    public ListNode sortList1(ListNode head) {
        // boundary
        if (head == null || head.next == null) return head;

        // 切分前后两半，各自排序，再merge
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) { // 结束时slow卡在中间节点
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode right = slow.next;
        slow.next = null;
        return merge(sortList1(head), sortList1(right));
    }
    // merge sort module, 合并的两个链表是有序的
    public ListNode merge(ListNode l1, ListNode l2) {
        // boudary check
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode aux = new ListNode(-1);
        ListNode ap = aux, p1 = l1, p2 = l2; // 初始状态和所需的三个指针，不要轻易污染链表头结点
        while (p1 != null && p2 != null) {  // 终止状态
            if (p1.val <= p2.val) {
                ap.next = p1; // 算法过程
                p1 = p1.next; // 迭代条件
                ap = ap.next;
            } else {
                ap.next = p2;
                p2 = p2.next;
                ap = ap.next;
            }
        }
        ap.next = p1 == null ? p2 : p1;
        return aux.next;
    }

    // quick sort
    public void quickSort(ListNode head, ListNode tail) { // 注意第二个参数
        if (head == tail) return; // 1. 终止条件
        ListNode pivot = partition(head, tail); // 2.初始状态 & 3. 算法操作，不污染递归变量，在收敛条件前
        quickSort(head, pivot); // 3_5. 收敛条件
        quickSort(pivot.next, tail);
    }
    public ListNode partition(ListNode head, ListNode tail) {
        ListNode p = head, i = head, j = head.next; // 1. 初始状态，i指针指向参考值最终次序，j指针用来遍历搂数据。注意i提前一个节点，循环中，i每次都是先走一下
        int pv = p.val;
        while (j != tail) { // 2. 终止状态
            if (j.val < pv) {
                i = i.next; // 3.5 迭代条件
                if (i.val != j.val) { // 3. 算法操作
                    swapValue(i, j);
                }
            }
            j = j.next;
        }
        swapValue(head, i);
        return i;
    }

    // quick sort
    public int[] quickSort (int[] a, int lo, int hi) {
        // boundary && end condition
        if (lo >= hi) return a;
        
        int pivot = partition(a, lo, hi);
        quickSort(a, lo, pivot-1);
        quickSort(a, pivot+1, hi);
        return a;
    }
    public int partition(int[] a, int lo, int hi) {
        int r = (int)(lo + Math.random()*(hi-lo+1)); //Or Random rand = new Java.util.Random(); rand.nextInt(hi-lo+1)
        swap(a, lo, r);
        int v = a[lo];
        int i = lo; // 1. 初始状态，i指针是参考值的最终次序索引, j指针是用来遍历数组搂数的
        for (int j = lo+1; j <= hi; j++) {
        if (a[j] < v) {
            i++; // 只有找到有比参考值小的情况，才把i值增加
            // non-stable here!
            if (j != i) {
            swap(a, i, j);
            }
            // // or use stable statements
            // int k = j;
            // while (k != i) {
            //    swap(a, k-1, k);
            // }
            // i++;
        }
        }
        swap(a, lo, i);
        return i;
    }

    
    // merge sort
    // Merge Sort. O(nlgn). key:
    public int[] mergeSort(int[] nums) {
        // boundary && end condition
        if (nums == null || nums.length < 2) return nums;

        int mid = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
        return mergeSort(mergeSort(left), mergeSort(right));
    }
    public int[] mergeSort(int[] l, int[] r) {
        int[] ret = new int[l.length + r.length];
        for (int k=0, i=0, j=0; k < ret.length; k++) {
            if (i >= l.length) {
                ret[k] = r[j++];
            } else if (j >= r.length) {
                ret[k] = l[i++];
            } else if (l[i] < r[j]) {
                ret[k] = l[i++];
            } else {
                ret[k] = r[j++];
            }
        }
        return ret;
    }

    // preorder
 // recursion
    public List preorderTraversal1(TreeNode root) {
        List list = new ArrayList<>();
        return helper(root, list);
    }
    public List helper(TreeNode root, List list) {
        // boundary
        if (root == null) return list;
        list.add(root.val);
        helper(root.left, list);
        helper(root.right, list);
        return list;
    }
    // iteration, stack
    public List preorderTraversal2(TreeNode root) {
        List list = new ArrayList<>();
        // boundary
        if (root == null) return list;

        // linkedList stack = new linkedList<>();
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop();
            list.add(n.val);
            if (n.right != null) {
                stack.push(n.right);
            }
            if (n.left != null) {
                stack.push(n.left);
            }
        }
        return list;
    }


    // inorder
    // recursion
    public List inorderTraversal1(TreeNode root) {
        // no need boundary check now

        // main logic
        // or use class variable
        List list = new ArrayList<>();
        helper(root, list);
        return list;
    }
    private void helper(TreeNode root, List list) {
        // recursion termination conditon
        if (root == null) {
            return;
        }
        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }
    // iteration
    public List inorderTraversal2(TreeNode root) {
        List list = new ArrayList<>();
        // boundary
        if (root == null) return list;

        linkedList stack = new linkedList<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode n = stack.pop();
            list.add(n.val);
            cur = n.right;
        }
        return list;
    }


    // postorder
    public List postorderTraversal1(TreeNode root) {
        // no need boundary check here

        // main logic
        // or use class variable
        List list = new ArrayList<>();
        helper(root, list);
        return list;
    }
    private void helper(TreeNode root, List list) {
        // recursion termination conditon
        if (root == null) {
            return;
        }
        helper(root.left, list);
        helper(root.right, list);
        list.add(root.val);
    }

    public List postorderTraversal2(TreeNode root) {
        List list = new ArrayList<>();
        // boundary
        if (root == null) return  list;

        linkedList stack = new linkedList<>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            // postOrder 根节点需要在栈中保留，直到栈空结束。每次需要通过用peek来获取头部，进而加入树的下层节点。
            // 在下层节点不为空，且下层节点没有入过栈的情况下，加入栈。
            // 栈的最大空间使树的左子树链和链上节点的右子节点的总和。

            // 先左子树各个节点入栈一波再出栈完，再柚子树入栈一波再出栈完，最后出栈根节点
            // 入栈的条件: 因为是后序遍历，出栈时父节点的right总是会指向right或left(左或者右节点可能会跳过)
            if ((cur.right != null || cur.left != null) && ((prev == null) || (cur.right != prev && cur.left != prev))){
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            } else {
                // 出栈的条件
                list.add(cur.val);
                stack.pop(); //其实就是弹出cur
                prev = cur;
                // OR
                // TreeNode t = stack.pop();
                // list.add(t.val);
                // prev = t;
            }
        }
        return list;
    }

    public List> levelOrder1(TreeNode root) {
        List> list = new ArrayList<>();
        // boundary
        if (root == null) return list;

        Queue q = new linkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            ArrayList tmp = new ArrayList<>();
            // 将一层的节点全部出对
            // 记录下一层的size
            int s = q.size();
            while (s > 0) {
                TreeNode n = q.poll();
                tmp.add(n.val);
                if (n.left != null) {
                    q.offer(n.left);
                }
                if (n.right != null) {
                    q.offer(n.right);
                }
                s--;
            }
            list.add(tmp);
        }