个人简介：
> 📦个人主页：赵四司机
> 🏆学习方向：JAVA后端开发
> 📣种一棵树最好的时间是十年前，其次是现在！
> 🔔博主推荐网站：牛客网 刷题|面试|找工作神器
> 💖喜欢的话麻烦点点关注喔，你们的支持是我的最大动力。
前言：
最近有不少小伙伴私信博主问我马上到秋招了，而自己平时没怎么练过算法，在算法这一块存在很大的弱势，应该怎么快速提升自己的算法水平。在这里我首先要说的是算法能力并不是可以快速掌握的，这需要慢慢积累，因为算法不仅考验我们的知识记忆深度，还考验我们的思维广度，因此很多很多大厂面试都会注重算法的考核。
其实博主一开始也没怎么练过算法题，但是对于中等简单的算法题还是可以通过一段时间的刷题来习得的。我最近就在一个叫牛客网的网站上面刷面试算法题，上面还很贴心给我们总结出了常考的题目，像剑指Offer、面试必刷Top101、面试高频榜单都有，先上图为证：
怎样，是不是很心动，下面我给你们介绍一下这个网站，传送门：牛客刷题神器
目录
一：反转链表
1.题目要求
2.解题思路
3.代码实现
二：链表中的节点每k个一组翻转
1.题目要求
2.解题思路
3.代码实现
三：合并两个排序的链表
1.题目要求
2.实现思路
3.代码实现
四：合并k个已排序的链表
1.题目要求
2.实现思路
3.代码实现
一：反转链表
1.题目要求
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
2.解题思路
反转链表可以考虑用栈来解决，将链表节点依次进栈，然后再出栈形成链表即可，但是这样空间复杂度就为O(n)级别。
我们可以做到在空间复杂度为O(1)级别情况下解决问题，可以做到原地反转链表。具体做法为摘掉当前节点然后将其链接到前面形成的链表后面，当然还需要另外一个节点记录尚未反转的链表表头。
3.代码实现
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {ListNode newHead = null;while(head != null) {ListNode temp = head.next;head.next = newHead;newHead = head;head = temp;}return newHead;}
}二：链表中的节点每k个一组翻转
1.题目要求
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
例如：
给定的链表是 1→2→3→4→5
对于 k = 2k=2 , 你应该返回 2→1→4→3→5
对于 k = 3k=3 , 你应该返回 3→2→1→4→5
2.解题思路
- step 1：每次从进入函数的头节点优先遍历链表k次，分出一组，若是后续不足k个节点，不用反转直接返回头。
- step 2：从进入函数的头节点开始，依次反转接下来的一组链表，反转链表同上。
- step 3：这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续。
3.代码实现
import java.util.*;/** public class ListNode {* int val;* ListNode next = null;* }*/public class Solution {/*** * @param head ListNode类 * @param k int整型 * @return ListNode类*/public ListNode reverseKGroup (ListNode head, int k) {// write code hereListNode tail = head;for(int i = 0; i < k; i++) {if(tail == null)return head;tail = tail.next;}//翻转链表ListNode pre = null;ListNode cur = head;while(cur != tail) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}head.next = reverseKGroup(tail,k);return pre;}
}三：合并两个排序的链表
1.题目要求
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
2.实现思路
初始化：定义cur指向新链表的头结点
操作：
- 如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值
- 否则，让l2指向下一个结点值
- 循环步骤1,2，直到l1或者l2为nullptr
- 将l1或者l2剩下的部分链接到cur的后面
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) {ListNode res = new ListNode(-1);ListNode cur = res;while(list1 != null && list2 != null) {if(list1.val < list2.val) {cur.next = list1;cur = list1;list1 = list1.next;} else {cur.next = list2;cur = list2;list2 = list2.next;}}cur.next = (list1 == null) ? list2 : list1;return res.next;}
}
四：合并k个已排序的链表
1.题目要求
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0≤n≤5000，每个节点的val满足 |val| <= 1000∣val∣<=1000
要求：时间复杂度 O(nlogn)O(nlogn)
示例1
输入：[{1,2,3},{4,5,6,7}]
复制返回值：{1,2,3,4,5,6,7}
示例2
输入：[{1,2},{1,4,5},{6}]
复制返回值：{1,1,2,4,5,6}
2.实现思路
可以考虑使用优先队列解决问题，优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)O(log_2n)O(log2n)，而每次取出堆顶元素都是直接取出。
具体实现：
- step 1：不管是Java还是C++都需要重载比较方法，构造一个比较链表节点大小的小顶堆。
- step 2：先遍历k个链表头，将不是空节点的节点加入优先队列。
- step 3：每次依次弹出优先队列中的最小元素，将其连接在合并后的链表后面，然后将这个节点在原本链表中的后一个节点（如果不为空的话）加入队列，类似上述归并排序双指针的过程。
3.代码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/import java.util.*;
public class Solution {public ListNode mergeKLists(ArrayList<ListNode> lists) {PriorityQueue<ListNode> queue = new PriorityQueue<>((val1,val2) -> val1.val - val2.val);for(int i =0; i < lists.size(); i++) {if(lists.get(i) != null) {queue.add(lists.get(i));}}ListNode res = new ListNode(-1);ListNode cur = res;while(!queue.isEmpty()) {cur.next = queue.remove();cur = cur.next;if(cur.next != null) {queue.add(cur.next);}}return res.next;}
}今天的题目介绍就到这，实践才是检验真理的唯一标准，算法光看还不行，必须得自己动手练习，传送门链接，一键直达练习场 ：牛客网 刷题|面试|找工作神器
