力扣爆刷第107天之CodeTop100五连刷21-25

一、103. 二叉树的锯齿形层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
思路：本题要求每层先从左往右遍历，下一层从右往左，再往下一层又变成了从左往右遍历，就是这种交替遍历，其实层序遍历的方式我们不需要改变，只需要改变记录的方式，对于每层出队节点收集时，如果该层是要求正序，那么把元素从尾部添加进新队列，如果该层要求逆序，那就从头部添加进队列，因为尾插法是正序，头插法是逆序，遍历后，然后再把收集到的数据添加进总集合中即可。

class Solution {
    List<List<Integer>> arrayList = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null) return arrayList;
        boolean flag = true;
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(flag) {
                    list.addLast(node.val);
                }else{
                    list.addFirst(node.val);
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            flag = !flag;
            arrayList.add(new ArrayList(list));
        }
        return arrayList;
    }
}

二、92. 反转链表 II

题目链接：https://leetcode.cn/problems/reverse-linked-list-ii/description/
思路：翻转链表中的一个片段，没啥技术含量，定位到为止，然后头插法，然后拼接尾部。

class Solution {
     public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode root = new ListNode(-1, head);
        ListNode p = root, pro = root, pre = null, end = null;
        for(int i = 0; i < left; i++) {
            pro = p;
            p = p.next;
        }
        pro.next = null;
        end = p;
        for(int i = left; i <= right; i++) {
            pre = p.next;
            p.next = pro.next;
            pro.next = p;
            p = pre;
        }
        end.next = p;
        return root.next;
    }
}

三、54. 螺旋矩阵

题目链接：https://leetcode.cn/problems/spiral-matrix/description/
思路：螺旋矩阵，控制上下左右边界，例如只要上边界小于等于下边界，就可以读取一行，如果左边界小于等于右边，就可以读取一列。

class Solution {
    List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = n-1, up = 0, down = m-1;
        while(list.size() < m * n) {
            if(up <= down) {
                for(int i = left; i <= right; i++) {
                    list.add(matrix[up][i]);
                }
                up++;
            }
            if(left <= right) {
                for(int i = up; i <= down; i++) {
                    list.add(matrix[i][right]);
                }
                right--;
            }
            if(up <= down) {
                for(int i = right; i >= left; i--) {
                    list.add(matrix[down][i]);
                }
                down--;
            }
            if(left <= right) {
                for(int i = down; i >= up; i--) {
                    list.add(matrix[i][left]);
                }
                left++;
            }
        } 
        return list;
    }
}

四、160. 相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
思路：经典题目，两个链表都先求长度，然后遍历统一长度，然后同步遍历即可。

public class Solution {
 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        int lenA = 0, lenB = 0;
        while(pa != null) {
            pa = pa.next;
            lenA++;
        }
        while(pb != null) {
            pb = pb.next;
            lenB++;
        }
        pa = headA;
        pb = headB;
        while(lenA < lenB) {
            pb = pb.next;
            lenB--;
        }
        while(lenA > lenB) {
            pa = pa.next;
            lenA--;
        }
        while(pa != null) {
            if(pa == pb) return pa;
            pa = pa.next;
            pb = pb.next;
        }
        return null;
    }
}

五、23. 合并 K 个升序链表

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/description/
思路：采用优先级队列，链表按照头部节点进行优先级排序，出队后然后再入队，然后一直出队统计即可。

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val-b.val);
        for(ListNode node : lists) {
            if(node != null) {
                queue.add(node);
            }
        }
        ListNode root = new ListNode();
        ListNode p = root;
        while(!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
            if(node.next != null) {
                queue.add(node.next);
            }
        }
        return root.next;
    }
}