☆25 K个一组翻转链表（找到待翻转链表的前面一个节点，后面一个节点，第一个节点，最后一个节点+链表尾指针置空链表翻转再连接；当待翻转链表长度小于k时直接返回）
/*
1.找到待翻转链表的前面一个节点，后面一个节点，第一个节点，最后一个节点
待翻转链表需要先断开，再翻转，再连接；
2.当待翻转链表长度小于k时，直接返回
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode newhead=new ListNode(-1);
newhead.next=head;
/*pre为待翻转元素的前面元素，
end为待翻转元素的最后一个元素;待翻转元素需要保证尾元素指针断开；
next为待翻转链表的后一个元素，
start为待翻转元素的第一个元素*/
ListNode pre=newhead;
ListNode end=pre;
while(end.next!=null){
for(int i=0;i<k&&end!=null;i++) end=end.next; //走k步
if(end==null) break;
//<----核心代码---->
//找到待翻转链表
ListNode next=end.next;
//d待翻转链表尾指针置空，翻转，再连接
end.next=null; //【重点】置空很关键
ListNode start=pre.next;
pre.next=reverse(start);
start.next=next;
//<----核心代码---->
pre=start;
end=pre;
}
return newhead.next;
}
public ListNode reverse(ListNode head){ //翻转链表
/**递归写法
if(head.next==null) return head;
ListNode newhead=reverse(head.next);
head.next.next=head;
head.next=null;
return newhead;
*/
//非递归写法
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode r=cur.next; //防止断链
cur.next=pre;
pre=cur;
cur=r;
}
return pre;
}
}
103二叉树的锯齿形层次遍历
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret=new ArrayList<>();
if(root==null) return ret;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int levelsize;
int sign=0;
while(!queue.isEmpty()){
levelsize=queue.size();
List<Integer> list=new ArrayList<>();
if(++sign%2==0){//逆序
Deque<Integer> stack=new LinkedList<>();
while(levelsize-->0){
TreeNode node=queue.poll();
stack.push(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
}else{ //顺序
while(levelsize-->0){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
ret.add(list);
}
return ret;
}
}
☆54 螺旋矩阵（记录上下边界是否越界，越界返回；不越界顺时针四周遍历）
/**
记录上下左右边界，依次右下左上顺时针遍历
1.其次向右移动，此时第一行因为已经使用过了，可以从图中删去，体现在代码中重新定义上边界
2.判断若重新定义后，上下边界交错，表示螺旋遍历结束；跳出循环，返回答案
否则继续遍历
*/
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ret=new ArrayList<>();
if(matrix==null||matrix.length==0||matrix[0].length==0) return ret;
int up=0,down=matrix.length-1,left=0,right=matrix[0].length-1;
while(true){
//从左往右遍历(最上层)
for(int col=left;col<=right;col++){
ret.add(matrix[up][col]);
}
if(++up>down) break; //++up为重置边界，如果up越界表示只有一行已经遍历完
//从上往下遍历(最右边)
for(int row=up;row<=down;row++){
ret.add(matrix[row][right]);
}
if(--right<left) break;
//从右往左遍历(最下边)
for(int col=right;col>=left;col--){
ret.add(matrix[down][col]);
}
if(--down<up) break;
//从下往上遍历(最左边)
for(int row=down;row>=up;row--){
ret.add(matrix[row][left]);
}
if(++left>right) break;
}
return ret;
}
}
415 字符串相加（类似两个链表节点相加，从后往前，结果逆序需要翻转）
/**
仿照两个链表节点相加
但是这里需要从后往前加，结果逆序
*/
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb=new StringBuilder("");
int i=num1.length()-1,j=num2.length()-1;
int tmp=0; //进位
while(i>=0||j>=0){
int val1=i<0? 0:num1.charAt(i)-'0';
int val2=j<0? 0:num2.charAt(j)-'0';
int sum=val1+val2+tmp;
tmp=sum/10;
sum=sum%10;
sb.append(sum);
i=i<0? i:i-1;
j=j<0? j:j-1;
}
if(tmp!=0){
sb.append(tmp);
}
return sb.reverse().toString(); //StringBuilder有内置反转算法
}
}
199 二叉树的右视图（层序遍历，每层只保存最右边的节点）
/**
层序遍历，每次只取这一层最右边的一个节点值
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret=new ArrayList<>();
if(root==null) return ret;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int levelsize=queue.size();
while(levelsize-->0){
TreeNode node=queue.poll();
if(levelsize==0) ret.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return ret;
}
}
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
88 合并两个有序数组（原地合并，从后往前合并，维护三个指针）
/**
从后往前合并
1.维护三个指针，i指向合并后数组位置，m指向nums1的元素位置，n指向nums2元素位置
2.当nums1全放完，nums2接着放
nums1没放完，nums2放完，结束
所以结束条件为nums2放完
*/
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i=nums1.length-1;
m--; //将m和n放到最后一个元素位置上
n--;
while(n>=0){
if(m>=0&&nums1[m]>nums2[n]){
nums1[i--]=nums1[m--];
}else{
nums1[i--]=nums2[n--];
}
}
}
}
143 重排链表（找到中间节点+翻转右半边链表+依次连接两个链表；使用ArrayList存储节点+双指针重连链表）
/**
解法一：
1.找到中间节点（偶数找到左半边最后一个节点，奇数只找到中间节点）
2.反转右半边链表
3.合并两个链表，依次连接
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
//1.找到链表的中间节点
ListNode slow=head,fast=head.next;
while(fast!=null&&fast.next!=null){
//当链表数量为奇数，fast为null，slow为中间节点
//当链表数量为偶数，fast.next为null,slow为左半边链表最后一个节点
slow=slow.next;
fast=fast.next.next;
}
ListNode newhead=slow.next;
slow.next=null;//【易错】左边链表末尾需要置空
//2.反转右半边链表
newhead=reverseList(newhead);
//3.合并链表
ListNode p1=head,p2=newhead;
while(p1!=null&&p2!=null){
ListNode r1=p1.next;
ListNode r2=p2.next;
p1.next=p2;
p2.next=r1;
p1=r1;
p2=r2;
}
}
public ListNode reverseList(ListNode head){
if(head==null||head.next==null) return head;
ListNode newhead=reverseList(head.next);
head.next.next=head;
head.next=null;
return newhead;
}
}
/**
方法二：
1.一次遍历，使用ArrayList存储节点
2.使用前后双指针，重排链表
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
//1.一次遍历，使用ArrayList存储节点
List<ListNode> list=new ArrayList<>();
ListNode cur=head;
while(cur!=null){
list.add(cur);
cur=cur.next;
}
//2.使用前后双指针，重排链表
int i=0,j=list.size()-1;
for(;i<j;i++,j--){
ListNode r1=list.get(i).next;
list.get(i).next=list.get(j);
list.get(j).next=r1;
}
//跳出循环，奇数i和j同时指向中间节点，偶数i>j，此时i指向最后一个节点
list.get(i).next=null;
}
}
版权声明：本文为weiguang2020原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。