📄个人主页：胖虎不秃头
?个人简介：Java领域新星创作者，随时准备跑路的大二学生
🔥精品专栏：有这一个就够了
🌈个人名言：知道的越多，不知道的越多
💥刷题神器：推荐一款算法刷题网站Nowcoder👉点击跳转刷题网站进行注册学习
1、反转链表
描述：
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
要求：
空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例：
示例1：
输入： {1,2,3}
返回值： {3,2,1}
示例2 输入：{}
返回值：{}
说明：空链表则输出空
题解：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//pre指针：用来指向反转后的节点，初始化为null
ListNode pre = null;
//当前节点指针
ListNode cur = head;
//循环迭代
while(cur!=null){
//Cur_next 节点，永远指向当前节点cur的下一个节点
ListNode Cur_next = cur.next;
//反转的关键：当前的节点指向其前一个节点(注意这不是双向链表，没有前驱指针)
cur.next = pre;
//更新pre
pre = cur;
//更新当前节点指针
cur = Cur_next ;
}
//为什么返回pre？因为pre是反转之后的头节点
return pre;
}
}
2、合并两个排序的链表
描述：
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0 \le n \le
10000≤n≤1000，-1000 \le 节点值 \le 1000?1000≤节点值≤1000
要求：
如输入{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}，转换过程如下图所示：
示例：
示例1 ：
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}
示例2：
输入： {-1,2,4},{1,3,4}
返回值： {-1,1,2,3,4,4}
题解：
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
// list1 list2为空的情况
if(list1 == null || list2 == null){
return list1 != null ? list1 : list2;
}
// 两个链表元素依次对比
if(list1.val <= list2.val){
// 递归计算 list1.next, list2
list1.next = Merge(list1.next, list2);
return list1;
}else{
// 递归计算 list1, list2.next
list2.next = Merge(list1, list2.next);
return list2;
} ## 标题
}
}
3、判断链表中是否有环
描述：
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
要求：
数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
示例：
示例1：
输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2：
输入： {1},-1
返回值： false
说明： 第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
题解：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode pos = head;
// 哈希表记录访问过的结点
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
// 判断结点是否被访问
if (visited.contains(pos)) {
return true;
} else {
// 结点记录添加到哈希表中
visited.add(pos);
}
// 遍历
pos = pos.next;
}
return false;
}
}
4、两个链表的第一个公共结点
描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
要求：
数据范围： n \le 1000n≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
示例：
示例1
输入： {1,2,3},{4,5},{6,7}
返回值： {6,7}
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入： {1},{2,3},{}
返回值： {}
说明： 2个链表没有公共节点 ,返回null，后台打印{}
题解：
public class Solution {
public int Lenth(ListNode pHead){//计算链表的长度
ListNode p = pHead;
int n = 0;
while(p != null){ //遍历每一个结点
n++;
p = p.next;
}
return n;
}
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int n1 = Lenth(pHead1);
int n2 = Lenth(pHead2);
if(n1 >= n2){ //链表1更长，链表1指针先走n1-n2步
int n = n1 - n2;
for(int i = 0; i < n; i++) //链表1先行
pHead1 = pHead1.next;
while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ //两个链表同时移动，直到有公共结点时停下
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
}
else{ //反之，则链表2先行n2-n1步
int n = n2 - n1;
for(int i = 0; i < n; i++)//链表2先行
pHead2 = pHead2.next;
while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
}
return pHead1;
}
}
5、删除有序链表中重复的元素-I
描述：
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次 例如： 给出的链表为1\to1\to21→1→2,返回1
\to 21→2. 给出的链表为1\to1\to 2 \to 3 \to 31→1→2→3→3,返回1\to 2 \to 31→2→3.
示例：
示例1
输入： {1,1,2}
返回值： {1,2}
示例2
输入： {}
返回值： {}
题解：
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates(ListNode head) {
ListNode node = new ListNode(-1); //创建一个头节点
node.next = head;
ListNode p= node;
ListNode cur = head;
while (cur!= null && cur.next != null) {//只要不为空，就继续
if(cur.val != cur.next.val) {//两个值不等的话
p = cur;
}
else {
while (cur.next != null && cur.val == cur.next.val)//相等的话
cur = cur.next;
p.next = cur.next;
}
cur = cur.next;
}
return node.next;//因为有头结点
}
}
算法的学习必须是有条理、有逻辑的由浅入深，一定要理论+实践结合，不管你是刚入门的小白，还是曾经学过相关知识，或者有一定基础，想要继续提升能力，又或者面试前突击想刷刷真题，都可以去牛客网练习！
牛客网做为国内内容超级丰富的IT题库，尤其是他的算法内容，从入门到大厂真题，完全覆盖了所有算法学习者的必备内容
从小白入门到某度、某音、某东的真实场景全部覆盖，只要想学习算法，那一定不能错过牛客网！而且内容全部免费，赶紧刷起来！👉点击跳转刷题网站进行注册学习