剑指offer专题训练|《剑指offer》专题—算法训练 day04
文章目录
- 《剑指offer》专题—算法训练day04
- 一、反转链表
-
- 思路一
- 思路二
- 二、合并有序链表
-
- 思路一
- 思路二
- 递归思路
- 三、树的子结构
-
- 思路
- 四、镜像二叉树
-
- 思路
- 未完待续...
《剑指offer》专题—算法训练day04
一、反转链表
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?
文章图片
思路一
定义三个指针，进行迭代，整体右移，边移动，边翻转，保证不会断链原链表
文章图片
第一次循环结束
文章图片
第二次循环结束
文章图片
第三次循环结束,跳出循环
文章图片
最后两个节点进行翻转
文章图片
原头节点的next 置为 null，更换新的头节点
文章图片
相关代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {// 设置三个引用指向连续的三个节点// 如果这个链表中 只有一个节点或者 没有节点时 ，直接返回 head
if(head== null || head.next == null){return head;
}// 不带头节点，至少还有2个节点
ListNode left = head;
// 指向第一个节点
ListNode mid = left.next;
// 指向第二个节点
ListNode right = mid.next;
// 指向第三个节点 ，可能为nullwhile(right != null){// 翻转操作
mid.next = left;
// 将中间节点的next 置为 前一个节点// 平移这三个节点
left = mid;
mid = right;
right = right.next;
}// 当上面这个循环走完时，最后一个节点 mid 还未反转，或者 这个链表中就只有两个节点
mid.next = left;
// 反转完毕后，头节点的next 置为 null
head.next = null;
// 反转后的开始节点置为头节点
head = mid;
return head;
}
}
思路二
可以采取头插法的思想进行翻转，可以每次把链表的第一个节点拿下来，头插进一个新的链表当中
相关代码
头插法进行反转链表
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {// 头插法进行反转链表ListNode new_head = null;
while(head!=null){// 把原链表的第一个节点拿下来
ListNode p = head;
// 第一个节点继续指
head = head.next;
// 然后这个节点头插进入新的链表当中
p.next = new_head;
new_head = p;
}return new_head;
}
}
二、合并有序链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?
文章图片
思路一
文章图片
有傀儡节点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1 ==null){return list2;
}if(list2 == null){return list1;
}// 建立一个傀儡节点
ListNode newHead = new ListNode(0);
ListNode tmp = newHead;
while(list1!=null && list2 !=null){if(list1.val 思路二
设立一个新的链表，同时定义头尾指针，
1.找到我们需要插入的节点
2.在原来表中删去该节点
3.将该节点尾插到新的链表当中
相关代码
无傀儡节点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1==null){return list2;
}if(list2 ==null){return list1;
}ListNode new_head = null;
// 新链表的头指针
ListNode new_end = null;
// 新链表的尾指针while(list1!=null && list2!=null){//1.找到我们要删除的节点
ListNode p = list1.val递归思路
重复的过程用递归来进行表示，缩小问题的规模
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1==null){return list2;
}if(list2 ==null){return list1;
}ListNode head = null;
// 新链表的头指针if(list1.val 三、树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?
文章图片
思路
二叉树都是递归定义的，所以递归操作是比较常见的做法
首先明白：子结构怎么理解，可以理解成子结构是原树的子树(或者一部分)
也就是说，B要是A的子结构，B的根节点+左子树+右子树，都在A中存在且构成树形结构
比较的过程要分为两步
1.先确定起始位置
2.在确定从该位置开始，后续的左右子树的内容是否一致
相关代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}}
*/
public class Solution {public boolean isSameChild(TreeNode root1,TreeNode root2){// 这个函数用来判断左右子树是否相等
if(root2 ==null){//原子树全部遍历完，说明左右子树相等
return true;
}
if(root1 == null){//目标子树全部遍历完，说明左右子树不相等
return false;
}if(root1.val != root2.val){return false;
}return isSameChild(root1.left,root2.left ) && isSameChild(root1.right,root2.right);
}public boolean HasSubtree(TreeNode root1,TreeNode root2) {if(root1 == null || root2== null){return false;
}boolean result = false;
//1.先找对应的起始位置
if(root1.val == root2.val){// 此时判断左右子树是否相等
result = isSameChild(root1,root2);
}// 如果resule 为 false ，那么没找到起始位置，继续从左子树找
if(result != true){result = HasSubtree(root1.left,root2);
}// 如果result 为 false ,那么没找到 起始位置，继续从右子树找
if(result !=true){result = HasSubtree(root1.right,root2);
}return result;
}
}
四、镜像二叉树
https://www.nowcoder.com/questionTerminal/a9d0ecbacef9410ca97463e4a5c83be7
文章图片
思路
二叉树的常规操作是递归思路，缩小问题的规模
这道题镜像二叉树，我们可以看到整颗树的左右子树都交换位置，我们缩小问题的规模，变成每颗子树的问题，每颗子树我们都需要进行交换左右子树的位置，进行递归操作.
相关代码
import java.util.*;
/*
* public class TreeNode {
*int val = 0;
*TreeNode left = null;
*TreeNode right = null;
*public TreeNode(int val) {
*this.val = val;
*}
* }
*/public class Solution {/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {// write code hereif(pRoot == null){return null;
}
TreeNode temp = pRoot.right;
pRoot.right = pRoot.left;
pRoot.left = temp;
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
}
??好了，今天的内容就结束了，希望大家多多练习~~
谢谢欣赏！！！
【剑指offer专题训练|《剑指offer》专题—算法训练 day04】《剑指offer》 算法训练day5 敬请期待…
未完待续…
推荐阅读
- 为什么文章被4个专题收录了阅读量却是个位数（）
- 【专题】怎样才能消除妊娠纹
- 剑指|剑指 Offer 13. 机器人的运动范围（dfs,bfs)
- 诗专题/秋花迎月
- 部署专题集合
- 文献阅读专题
- 我是来搞笑的|我是来搞笑的|专题投稿直男
- 剑指offer60.n个骰子的点数
- 剑指offer——最小的K个数
- B|B 【小组记事】230-6组 专题会议---家庭教育