大家好啊，我是小鲨鱼，最近一直更新自己的题解，一直在刷题也没有做一个总结和分类，那就从今天开始吧。以后本文章将会持续更新题解和题型，以此记录我的刷题之路。
题型还很少很少，以后会慢慢补充哒。
刷题总结![
文章目录- 刷题总结
- 结构
- 数组
- 队列
- 链表
- 删除节点
- 删除链表中的重复元素
- 有序链表
- 无序链表
- 删除链表中目标值的节点
- 反转链表
- 全部反转
- 部分反转
- 合并链表
- 有序链表
- 无序链表
- 相交链表
- 链表无环
- 链表有环
- 环形链表
- 回文链表
- 修改链表
- 不做修改
- 链表求和
- 栈
- 串
- 堆
- 树
- 二叉树
- 遍历问题
- 递归
- 非递归
- 层序遍历
- 搜索树
- kth问题
- 平衡树
- 深度问题
- 图
- 哈希表
- 算法
- 排序
- 递归
- 二分查找
- 回溯
- 分治
- 贪心
- KMP
- 动态规划
- 深度优先搜索
- 广度优先搜索
- 小技巧
- 双指针
- 位运算
] 结构
数组 队列 链表
- 数组
- 队列
- 链表
- 栈
- 串
- 堆
- 树
- 图
- 哈希表
- 删除节点
- 反转链表
- 合并链表
- 相交链表
- 环形链表
- 回文链表
- 链表求和
删除节点
- 删除目标元素：此类题较为简单，为链表的基本 *** 作，只需把目标元素的下一节点的值赋值给当前节点，然后让当前节点的next指向下一节点的next即可。
- 删除重复元素
- 有序：通过一次遍历，两两比较，遇到重复元素删除即可（删除 *** 作需要有一个节点来记录当前节点的前驱），只需两个节点。
- 无序：定义三个指针cur1,cur2,cur3，cur1在前，cur2从cur1的next开始遍历，遇到重复元素删除，如果cur2走到尾巴，cur1向后走，cur2仍从cur1的next开始往后遍历。
删除链表中的重复元素
- 有序链表
- 重复元素个数保留为1
- 重复元素全部删除
- 无序链表
有序链表
例题：83. 删除排序链表中的重复元素
题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lb4VIcil-1634570556751)(C:Users左宗帅AppDataRoamingTyporatypora-user-imagesimage-20211017195651336.png)]
解题思路
一次遍历:已知所给链表为升序，所以只需遍历一次，如果相邻元素相同删除后一个节点即可。
变量：cur1,cur2
从head开始，始终让cur1在前，cur2在后，遇到重复元素删除cur2即可。
注：此题只需让每个元素个数保持为1即可，所以当头节点元素重复时不需要删除头节点，即不需要伪造头节点。
代码
class Solution {
public ListNode deleteDuplicates ( ListNode head ) {
if(head == null) {
return null;
}
ListNode cur1 = head;
ListNode cur2 = cur1.next;
while(cur2 != null){
if(cur1.val == cur2.val){
cur1.next = cur2.next;
}else{
cur1 = cur1.next;
}
cur2 = cur2.next;
}
return head;
}
}
无序链表
代码
public class Solution {
public ListNode deleteDuplicates( ListNode head ){
if(head == null){
return null;
}
ListNode cur1 = head;
ListNode cur2 = cur1.next; //用来与cur1进行比较是否相同
ListNode cur3 = cur1; //用来记录cur2的前驱节点
while(cur1 != null){
if(cur1.val == cur2.val){ //如果值相同 删除cur2
cur3.next = cur2.next;
}
cur2 = cur2.next; //无论是否相同cur2都要往后走
if(cur2 == null){ //如果cur2走到尾巴
cur1 = cur1.next; //cur1走一步
cur2 = cur1.next; //cur2仍在cur1的后面
}
}
return head;
}
}
删除链表中目标值的节点
反转链表
全部反转
- 全部反转：此类型只需把该链表全部反转过来即可，如果有不存在值的头节点，要考虑换头的 *** 作。
- 头插法
- 递归
- 迭代
- 部分反转：此类型的题会给出一个反转部分的开头与结尾，需要把链表中对应下标的部分翻转过来。
例题：206. 反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e6tdG3VO-1634570556753)(C:Users左宗帅AppDataRoamingTyporatypora-user-imagesimage-20211017205947234.png)]
解题思路
- 头插法
- 递归
- 迭代
代码
//头插法
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode p = head;
ListNode cur1 = p.next;
ListNode cur2 = cur1;
while(cur2 != null){
cur2 = cur2.next;
cur1.next = p;
p = cur1;
cur1 = cur2;
}
head.next = null;
return p;
}
}
部分反转 合并链表 有序链表
例题：21. 合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oqRTUpiN-1634570556755)(C:Users左宗帅AppDataRoamingTyporatypora-user-imagesimage-20211017210652297.png)]
解题思路
双指针：新建一个头节点**l**，以给出的l1和l2为指针，分别遍历两个链表，每遍历一个节点，比较l1和l2的值，将较小的值连接在新链表节点的后面,返回新建头节点的next即为所求。
变量：节点l和cur，cur用作记录头节点。
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode l=new ListNode(0);
ListNode cur = l;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next =l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null){
cur.next=l1;
}
if(l2 != null){
cur.next = l2;
}
return l.next;
}
}
无序链表 相交链表 链表无环
例题：160. 相交链表
题目描述/
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
示例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qG1HvLRa-1634570556757)(C:Users左宗帅AppDataRoamingTyporatypora-user-imagesimage-20211017234904551.png)]
解题思路
两次遍历：
- 定义两个节点cur1,cur2,分别遍历两个链表，并用一个变量记录两个链表长度的差值。
- 比较两个链表的尾巴（非null），如果不一样，说明两链表不相交，直接返回null。
- 如果一样，通过差值将cur1定义为长链表，将cur2定义为短链表。然后让cur1先走差值步（如果两链表相交，从相交部分开始后面长度均相同），再让cur2跟着一起走，当cur1与cur2相等时，当前节点即为第一个公共节点。
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null && headB == null){
return null;
}
ListNode cur1 = headA;
ListNode cur2 = headB;
int len=0;
while(cur1 != null){
cur1 = cur1.next;
len ++;
}
while(cur2 ! =null){
cur2 = cur2.next;
len--;
}
cur1 = len > 0 ? headA : headB;
cur2 = cur 1 == headA ? headB : headA;
len = Math.abs(len);
while( len != 0 ){
cur1 = cur1.next;
len --;
}
while(cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}
链表有环
环形链表
例题：141. 环形链表
题目描述：
给定一个链表，判断链表中是否有环。如果链表中存在环，则返回 true 。 否则，返回 false 。
示例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lNP0Db0s-1634570556759)(C:Users左宗帅AppDataRoamingTyporatypora-user-imagesimage-20211017231702727.png)]
解题思路
- 哈希表：遍历该链表，把每一个遇到的节点放入表中，如果放入失败，则该链表中有环，当前不能放入的节点即为第一个入环节点。
- 快慢指针：
- 快指针一次走两步，慢指针一次走一步。如果该链表无环，快指针会先走到null，说明两链表不相交，直接返回null即可。
- 如果有环，两指针最终会相遇，然后结束循环。此时让快指针回到头节点，两指针同时开始走相同步，相交的第一个节点即为入环节点。
代码
//哈希表
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet count = new HashSet<>();
while(count.add( head )&&head != null){
head=head.next;
}
return head;
}
}
//快慢指针
public class Solution{
public ListNode detectCycle(ListNode head){
ListNode fast = head,low =head;
while(low != fast){
if(fast == null || fast.next == null){
return null;
}
fast = fast.next.next;
low = low.next;
}
fast = head;
while(low != fast){
low = low.next;
fast = fast.next;
}
return fast;
}
}
回文链表
修改链表 不做修改 链表求和
允许修改
- 快慢指针
不做修改
- 一次遍历+额外数组+双指针：
例题：面试题 02.05. 链表求和
题解：面试题 02.05(mid). 链表求和(Java)_m0_51809739的博客-CSDN博客
栈 串 堆 树 二叉树遍历问题 递归 非递归 层序遍历 搜索树 kth问题 平衡树 深度问题 图 哈希表
- 前中后遍历
- 搜索树
- 平衡树
- 深度问题
算法
排序 递归 二分查找 回溯 分治 贪心 KMP 动态规划 深度优先搜索 广度优先搜索 小技巧 双指针 位运算
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）