1. 反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
分析
定义两个节点next:保存当前节点(head)的下一个节点(head.next)因为下面需要让head.next指向pre,防止链表断裂
pre:当前节点的前一个节点用来让head.next指向pre
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode next = null;
ListNode pre = null;
while(head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
2. 合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调递增规则。
分析
- 定义一个链表它就是需要返回的合并链表
- 定义一个辅助节点,用来拼接链表
- 当两个链表都不为空时,比较当前节点的值的大小,如果list1.val<list2.val
- 把辅助节点指向list1节点,并让list1节点后移,如果list1.val>=list2.val,反之
- 最后让辅助节点后移,当有一个链表的list节点为null时
- 让辅助节点指向另一个list节点,返回头节点的next
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if(list1!=null)cur.next = list1;
if(list2!=null)cur.next = list2;
return head.next;
}
}
//递归解法每次返回最小的节点
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
}
3. 树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
分析
-
这棵大树的子结构有：
4 和 5 对应的两棵子树
3 本身自己完整的一棵树
而里面的小框圈出来的不是 3 这棵大树的子树！
理解后可以写代码了，如果子树先达到 null ，那么一定是其子树
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return judgeSubTree(root1, root2)||judgeSubTree(root1.left, root2)||judgeSubTree(root1.right, root2);
}
private boolean judgeSubTree(TreeNode root1,TreeNode root2){
//如果Tree2已经遍历完了都能对应的上，返回true
if(root2 == null){
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if(root1 == null){
return false;
}
//如果其中有一个点没有对应上，返回false
if(root1.val != root2.val){
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return judgeSubTree(root1.left, root2.left)&&judgeSubTree(root1.right, root2.right);
}
}
4. 二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
分析
- 如果当前根节点为null,return;当前根节点的左节点和右节点都为null,return
- 定义一个辅助变量,保存root.left,方便交换左右节点
- 接着判断当前根节点的左节点是否为空,不为空把它当作根节点进行递归
- 右节点同理
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
if(root.left == null&&root.right == null){
return;
}
TreeNode tn = root.left;
root.left = root.right;
root.right = tn;
if(root.left != null){
Mirror(root.left);
}
if(root.right != null){
Mirror(root.right);
}
}
}
5. 顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
分析
简单来说，就是不断地收缩矩阵的边界
定义四个变量代表范围，up、down、left、right
- 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
- 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
- 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
- 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错
代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(matrix == null || matrix.length==0){
return list;
}
int up = 0;
int down = matrix.length-1;
int left = 0;
int right = matrix[0].length-1;
while(true){
//向右
for(int i = left;i<=right;i++){
list.add(matrix[up][i]);
}
if(++up>down){
break;
}
//向下
for(int i = up;i<=down;i++){
list.add(matrix[i][right]);
}
if(--right<left){
break;
}
//向左
for(int i = right;i>=left;i--){
list.add(matrix[down][i]);
}
if(--down<up){
break;
}
//向上
for(int i = down;i>=up;i--){
list.add(matrix[i][left]);
}
if(++left>right){
break;
}
}
return list;
}
}
