力扣爆刷第153天之TOP100五连刷（相交、翻转、排序链表、螺旋矩阵、锯齿二叉树）
文章目录
一、103. 二叉树的锯齿形层序遍历
题目链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
思路：本题很有意思，要求层序遍历，但是需要从左往右，再从右往左，以此往复。但本质上还是层序遍历，所以不要想复杂了，我们要维持层序遍历的框架不要动，正常的使用层序遍历，但是在出队收集元素时，使用一个双向队列来收集，按照偶数层和奇数层分别从右边添加进入队列和从左边添加进入队列。即可。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean flag = true;
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;
result.add(list);
}
return result;
}
}
二、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 start = root, end = null, p = root, q = null;
for(int i = 0; i < left; i++) {
start = p;
p = p.next;
}
start.next = null;
end = p;
for(int i = left; i <= right; i++) {
q = p.next;
p.next = start.next;
start.next = p;
p = q;
}
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 n = matrix.length, m = matrix[0].length, left = 0, right = m, up = 0, down = n;
while(list.size() < n*m) {
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-1]);
}
right--;
}
if(up < down) {
for(int i = right-1; i >= left; i--) {
list.add(matrix[down-1][i]);
}
down--;
}
if(left < right) {
for(int i = down-1; i >= up; i--) {
list.add(matrix[i][left]);
}
left++;
}
}
return list;
}
}
四、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 = node;
if(node.next != null) {
queue.add(node.next);
}
}
return root.next;
}
}
五、160. 相交链表
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
思路：求相交链表，也是非常经典的一个题目，只需要分别求长度，然后对其长度，逐一比较即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
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;
for(int i = lena; i < lenb; i++) {
pb = pb.next;
}
for(int i = lenb; i < lena; i++) {
pa = pa.next;
}
while(pa != null) {
if(pa == pb) return pa;
pa = pa.next;
pb = pb.next;
}
return null;
}
}