1. 反轉(zhuǎn)鏈表
題目描述
輸入一個鏈表图谷，反轉(zhuǎn)鏈表后主之，輸出新鏈表的表頭变汪。
分析
定義兩個節(jié)點next:保存當前節(jié)點(head)的下一個節(jié)點(head.next)因為下面需要讓head.next指向pre,防止鏈表斷裂
pre:當前節(jié)點的前一個節(jié)點用來讓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. 合并兩個排序的鏈表
題目描述
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表催首，當然我們需要合成后的鏈表滿足單調(diào)遞增規(guī)則。
分析
- 定義一個鏈表它就是需要返回的合并鏈表
- 定義一個輔助節(jié)點,用來拼接鏈表
- 當兩個鏈表都不為空時,比較當前節(jié)點的值的大小,如果list1.val<list2.val
- 把輔助節(jié)點指向list1節(jié)點,并讓list1節(jié)點后移,如果list1.val>=list2.val,反之
- 最后讓輔助節(jié)點后移,當有一個鏈表的list節(jié)點為null時
- 讓輔助節(jié)點指向另一個list節(jié)點,返回頭節(jié)點的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;
}
}
//遞歸解法每次返回最小的節(jié)點
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. 樹的子結(jié)構(gòu)
題目描述
輸入兩棵二叉樹A泄鹏，B郎任，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）
分析
-
這棵大樹的子結(jié)構(gòu)有：
4 和 5 對應(yīng)的兩棵子樹
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已經(jīng)遍歷完了都能對應(yīng)的上车猬，返回true
if(root2 == null){
return true;
}
//如果Tree2還沒有遍歷完霉猛，Tree1卻遍歷完了。返回false
if(root1 == null){
return false;
}
//如果其中有一個點沒有對應(yīng)上珠闰，返回false
if(root1.val != root2.val){
return false;
}
//如果根節(jié)點對應(yīng)的上惜浅，那么就分別去子節(jié)點里面匹配
return judgeSubTree(root1.left, root2.left)&&judgeSubTree(root1.right, root2.right);
}
}
4. 二叉樹的鏡像
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像伏嗜。
分析
- 如果當前根節(jié)點為null,return;當前根節(jié)點的左節(jié)點和右節(jié)點都為null,return
- 定義一個輔助變量,保存root.left,方便交換左右節(jié)點
- 接著判斷當前根節(jié)點的左節(jié)點是否為空,不為空把它當作根節(jié)點進行遞歸
- 右節(jié)點同理
代碼
/**
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. 順時針打印矩陣
題目描述
輸入一個矩陣坛悉，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如承绸，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字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;
}
}
