链表题

1.反转链表

//1.定义当前节点得下一个节点
ListNode temp = cur.next;
// 2.下一个节点指向上一个
cur.next = pre;
// 3. 移动上一个节点和当前节点
pre = cur;
cur = temp;

2.一段链表反转其中某一段
见图：https://www.acwing.com/solution/content/174/

1.走到反转的前一个节点
然后记录下来ListNode a = cur;
2.反转n - m 次，
3. a.next.next = c;
4. a.next = b;

1. 合并k个有序链表时间复杂度在nlogn

//归并思想
 public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return dfs(lists, 0, lists.size() - 1);
    }

    ListNode dfs(List<ListNode> lists, int l, int r) {
        if (l > r) return null;
        if (l == r) return lists.get(l);
        int mid = l + r >> 1;
        return merge(dfs(lists, l, mid), dfs(lists, mid + 1, r));
    }

4.指针排序 归并思想 两端合并成有序一段
5.有无环(快慢指针)

快慢指针 fast = head.next  保证slow在中间
         slow = head;

树

1.验证一棵树的对称性，深度，翻转性质。反转要传入一颗完整得树
2.前序，中序或者后序中序构造一棵二叉树
3.层序遍历 衍生出来的
3.1构造分层 或者不分层 或者改动指针的 https://www.acwing.com/file_system/file/content/whole/index/content/3592/
3.2 最大宽度的

List<List<Integer>> ans = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
List<Integer> level = new ArrayList<>();
q.add(root);
q.add(null); // 每层最后一个放置null作为结束

while(!q.isEmpty()) {
    // 每一层个数
    int size = q.size();
    // 每一个
    TreeNode t = q.poll();

    if(t != null) {
        level.add(t.val);
        if (t.left != null) q.add(t.left);
        if (t.right != null) q.add(t.right);
    } else {
        if (!q.isEmpty()) q.add(null);

        ans.add(new ArrayList<>(level));
        level.clar();
    }

}
return ans;

栈

1. 1. 字符串解码[双栈]