链表
| 1天前 | #146 LRU 缓存 | 中等 | 1 次 |
|---|---|---|---|
| 1 天前 | #23 合并 K 个升序链表 | 困难 | 1 次 |
| 1 天前 | #148 排序链表 | 中等 | 1 次 |
| 1 天前 | #138 随机链表的复制 | 中等 | 1 次 |
| 1 天前 | #25 K 个一组翻转链表 | 困难 | 2 次 |
| 1 天前 | #24 两两交换链表中的节点 | 中等 | 3 次 |
| 1 天前 | #19 删除链表的倒数第 N 个结点 | 中等 | 4 次 |
| 1 天前 | #2 两数相加 | 中等 | 4 次 |
| 1 天前 | #21 合并两个有序链表 | 简单 | 3 次 |
| 1 天前 | #141 环形链表 | 简单 | 20 次 |
| 1 天前 | #142 环形链表 II | 中等 | 4 次 |
| 1 天前 | #234 回文链表 | 简单 | 1 次 |
| 1 天前 | #206 反转链表 | 简单 | 6 次 |
| 1 天前 | #160 相交链表 | 简单 | 3 次 |
链表备注： 1、环形链表判断条件
2、删除链表节点判断条件
3、k个一组翻转链表 赋值条件 翻转链表递归（赋值条件）
4、随机链表复制 ，新链表条件 以及 递归结束条件
5、lru缓存 （一般会不会考） 记一下简单方式实现
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
# 链表相交
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
}
}
思路
1、分别对两个链表定义两个指针
2、while 判断两个指针是否相等 （内部条件 a指针空了就赋值b的节点，b也是如此，一直判断下去）
3、返回任一指针即可（因为肯定存在相交的）
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 翻转链表
class Solution {
public ListNode reverseList(ListNode head) {
}
}
递归做简单
1、判断结束条件 head 为空 以及他的next为空 返回 head
2、否则将head.next 传递 进行递归，得到 【翻转后链表】
3、这时候 head.next.next 赋值为 head （此时的head相当于下一次的next，这里就实现了翻转后的赋值）
4、head.next 赋值为 null 断开链表
5、最终返回 【翻转后链表】
双指针翻转
1、定义第一个指针 res 为null ， 第二个 now 为当前head
2、while now不为空循环
3、开始赋值 a、定义一个item 为 now的next， b、now的next 为res， c、res为now d、 now为item （有点绕的）
4、最终返回 res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 回文链表
class Solution {
public ListNode reverseList(ListNode head) {
}
}
思路
1、这个简答，直接把链表转化为list（有序的）
2、双指针判断
1
2
3
4
5
6
7
2
3
4
5
6
7
# 环形链表 1、2
class Solution {
public ListNode hasCycle(ListNode head) {
}
}
判断一个链表有没有环
1、快慢指针，但是第二个指针得定义为head.next
2、while 循环对快指针以及快指针的next判断
3、内部两个指针相交则有环
4、快指针比满指针循环多一个next
找到相交节点的第一个位置
1、定义两个一模一样的指针
2、选一个为快指针，判断条件一样，但是其循环必须放在while的首行
3、两指针相交后 在合源链表比较
4、两指针任选一个 为index1 head为index2
5、只要两个index不相等 一直 while循环判断
6、之后任选一个index返回即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 合并链表（需要创建新链表
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
}
}
思路
1、需要定义一个新的链表
统一思路：
ListNode res = new ListNode(-1);
ListNode p = res;
对之后都是对p操作 ，最后返回res.next;
2、while 循环 list1 || list2 都不为null
3、比较val的大小 选择赋值 并且进行next循环
4、while完之后 肯定还有没赋值完成的 然后判断 直接把剩下的list赋值到p后面
5、返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 两数相加（需要创建新链表
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
}
思路：
1、定义一个新链表
2、定义一个item 方便对溢出10的值进行赋值
3、l1跟l2只有有一个不为空就进行while循环
4、内部定义 first跟second 初始值为0，根据链表的值进行赋值
5、 sum的值为item +first+ second
6、当前节点的值sum %10
7、下一次item的值为 sum /10 然后指针进入循环
8、最后判断item是否为空 来进行最后节点的赋值
9、最后返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 删除倒数第n个节点 （需要创建新链表
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
}
}
思路：
0、定义一个新链表
1、快慢指针针对新链表，定义两个一模一样的
2、快指针先走n步
3、while循环快指针的next，慢指针也跟着走 （之所以快指针的next是因为新链表这里next了）
4、最后 slow.next = slow.next.next;
5、返回
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 两两交换结点
class Solution {
public ListNode swapPairs(ListNode head) {
}
}
思路：
1、递归
2、统一的结束条件 head 以及head的next为null就返回head；
3、然后将【head的的next】记录下来为node
4、记录下来的node的next进行递归 返回为swap
5、然后【head的next】为 swap
6、node 的next为head；
7、最终返回node
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# k个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
}
}
思路：
1、定义一个新链表 以及两个一模一样的指针 p1 p2
2、while 循环p2不为空
3、然后p2走k步，这个时候for循环的判断条件增加p2不为空（否则会空指针
4、之后判断p2为空直接结束循环
5、然后开始赋值环节 a、记录p2的next为end b、然后p2.next为null 断开链 c、记录p1的next为start d、然后p1.next调用翻转链表函数进行翻转 传值为start， 这样就得到这一段的翻转链表， e、然后start的next赋值为end，再接上上一段 f、然后 p1 p2指针都赋值为start，开始新的下一段while循环
6、最后返回res.next
7、翻转函数同上
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 随机链表的复制
class Solution {
// 定义hash
public ListNode swapPairs(ListNode head) {
}
}
思路：
1、hashmap + 递归
2、返回条件依然是head以及head next为空 返回head
3、if条件判断 head是否存在hash 在 直接返回value 否则进行组装
4、首先得到head next，然后放到map中
5、然后对新的node的next 以及 指针 进行head的赋值
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 排序链表
class Solution {
public ListNode swapPairs(ListNode head) {
}
}
思路：
1、先把链表转换成list
2、对list进行排序
3、再将list转化成链表
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 合并k个升序链表
class Solution {
public ListNode swapPairs(ListNode head) {
}
}
思路：
1、分解成 【合并两个升序链表】
1
2
3
4
5
6
7
2
3
4
5
6
7
# lru缓存
class Solution {
public ListNode swapPairs(ListNode head) {
}
}
思路：
1、简单点 直接继承linkedHashMap
1
2
3
4
5
6
7
2
3
4
5
6
7
上次更新: 2024/03/26, 9:03:00