跳到主要内容 Java 算法 Hot100 链表类型题目详解笔记 | 极客日志
Java java 算法
Java 算法 Hot100 链表类型题目详解笔记 LeetCode Hot100 系列中关于链表类型的 Java 算法题解，涵盖相交链表、反转链表、回文链表、环形链表检测与入口、合并有序链表、两数相加、删除倒数节点、节点交换、K 组翻转、随机链表复制、排序链表、合并 K 个链表以及 LRU 缓存等经典问题。内容包含具体代码实现、思路解析及关键知识点总结，重点讲解了快慢指针、虚拟头节点、递归、哈希映射及双端队列等常用技巧，适合复习与面试准备。
编程诗人 发布于 2026/3/21 更新于 2026/4/18 160. 相交链表
LeetCode 160
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
具体题解
public class Solution {
public ListNode getIntersectionNode (ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while (A != B) {
if (A != null ) {
A = A.next;
} else {
A = headB;
}
if (B != null ) {
B = B.next;
} else {
B = headA;
}
}
return A;
}
}
思路解析
假设有交点的话，A 长度 + B 部分长度 = B 长度 + A 部分长度。最终 A 与 B 一定会相同，可能是 null 也可能是共同节点。
必会知识
无
206. 反转链表
LeetCode 206
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
具体题解
class Solution {
public ListNode reverseList (ListNode head) {
return recur(head, null );
}
public ListNode recur (ListNode cur, ListNode pre) {
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
while
null
ListNode
tmp
=
return
思路解析 着眼于当前节点与上一节点。调整当前节点指向上一节点，再重新换 cur 与 pre 进行下一轮。
必会知识
234. 回文链表 给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
具体题解 class Solution {
public boolean isPalindrome (ListNode head) {
List<Integer> vals = new ArrayList <>();
ListNode tmp = head;
while (tmp != null ) {
vals.add(tmp.val);
tmp = tmp.next;
}
int front = 0 ;
int back = vals.size() - 1 ;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false ;
}
front++;
back--;
}
return true ;
}
}
思路解析
必会知识
集合比较时使用 equals()，因为装的元素的 Integer
141. 环形链表 给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true。否则，返回 false。
具体题解 public class Solution {
public boolean hasCycle (ListNode head) {
if (head == null ) {
return false ;
}
ListNode A = head;
ListNode B = head;
while (A != null && A.next != null ) {
A = A.next.next;
B = B.next;
if (A == B) {
return true ;
}
}
return false ;
}
}
思路解析 使用快慢指针，如果有环最终一定有 A==B。如果无环，最终一定有某一方为 null。
必会知识
142. 环形链表 II 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
具体题解 public class Solution {
public ListNode detectCycle (ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break ;
}
}
if (fast == null || fast.next == null ) {
return null ;
} else {
fast = head;
}
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
思路解析 使用快慢指针 + 数学关系推导。当 A==B 时，退出循环，让 A 从 head 重新每次加一，最后一定会在节点处相遇。
必会知识
21. 合并两个有序链表 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
具体题解 class Solution {
public ListNode mergeTwoLists (ListNode list1, ListNode list2) {
ListNode dummy = new ListNode ();
ListNode dummy1 = dummy;
while (list1 != null && list2 != null ) {
if (list1.val <= list2.val) {
dummy.next = list1;
dummy = dummy.next;
list1 = list1.next;
} else {
dummy.next = list2;
dummy = dummy.next;
list2 = list2.next;
}
}
if (list1 == null ) {
dummy.next = list2;
} else {
dummy.next = list1;
}
return dummy1.next;
}
}
思路解析 通过 dummy 头避免边界处理麻烦，将剩余两条链挨个对比接到 dummy 头后。
必会知识 ListNode dummy = new ListNode <>();
ListNode dummy1 = dummy;
2. 两数相加 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
具体题解 class Solution {
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
ListNode ans = null ;
ListNode ans1 = ans;
int carry = 0 ;
while (l1 != null || l2 != null ) {
int n1 = l1 != null ? l1.val : 0 ;
int n2 = l2 != null ? l2.val : 0 ;
int sum = n1 + n2 + carry;
if (ans == null ) {
ans = ans1 = new ListNode (sum % 10 );
} else {
ans.next = new ListNode (sum % 10 );
ans = ans.next;
}
carry = sum / 10 ;
if (l1 != null ) {
l1 = l1.next;
}
if (l2 != null ) {
l2 = l2.next;
}
}
if (carry > 0 ) {
ans.next = new ListNode (carry);
}
return ans1;
}
}
思路解析 这题细节处较多。在判断还有数可加时再 new ListNode，避免出现多出的链表头。对 carry 处理要细心，退出循环后 carry 仍可能有值。
必会知识
19. 删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
具体题解 class Solution {
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode dummy = new ListNode (0 , head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0 ; i < n; i++) {
first = first.next;
}
while (first != null ) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
思路解析 关键在于如何定位倒数第 k 个节点。为消除倒数第 k 个节点是头节点的影响，使用 dummy 辅助。用 first 节点先走 k 个，second 与 first 节点再一起走，走到 first=null。则 second 在倒数第 k 个的位置。
必会知识
24. 两两交换链表中的节点 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
具体题解 class Solution {
public ListNode swapPairs (ListNode head) {
ListNode dummy = new ListNode (0 , head);
ListNode dummy1 = dummy;
while (dummy != null && dummy.next != null && dummy.next.next != null ) {
ListNode node1 = dummy.next;
ListNode node2 = dummy.next.next;
dummy.next = node2;
node1.next = node2.next;
node2.next = node1;
dummy = node1;
}
return dummy1.next;
}
}
思路解析 注意力放在上一节点，当前节点，下一节点上。最开始利用 dummy 充当上一节点，重新连接这三个节点的位置，再将 dummy 赋值为下一轮次的'上一节点'。
必会知识
25. K 个一组翻转链表 给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
具体题解 class Solution {
public ListNode reverseKGroup (ListNode head, int k) {
ListNode cur = head;
for (int i = 0 ; i < k; i++) {
if (cur == null ) return head;
cur = cur.next;
}
ListNode dummy = reverseKGroup(cur, k);
for (int i = 0 ; i < k; i++) {
ListNode tmp = head.next;
head.next = dummy;
dummy = head;
head = tmp;
}
return dummy;
}
}
思路解析 利用递归的思想，但更主要的是反转链表中的模板思路。反转链表的思路代入到这里，上一节点即为 dummy（当前 k 节点之外的节点，由递归返回），当前节点即为 head。流程是先递归，再反转。
必会知识
138. 随机链表的复制 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y。那么在复制链表中对应的两个节点 x 和 y，同样有 x.random --> y。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null。 你的代码只接受原链表的头节点 head 作为传入参数。
具体题解 class Solution {
public Node copyRandomList (Node head) {
if (head == null ) return null ;
Node cur = head;
Map<Node, Node> map = new HashMap <>();
while (cur != null ) {
map.put(cur, new Node (cur.val));
cur = cur.next;
}
cur = head;
while (cur != null ) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
思路解析 这里的神来之笔是，利用 hashmap 存入与待复制节点一模一样的节点，并且完成映射关系。
必会知识
148. 排序链表 给你链表的头结点 head，请将其按升序排列并返回排序后的链表。
具体题解 class Solution {
public ListNode sortList (ListNode head) {
List<Integer> list = new ArrayList <>();
ListNode node = head;
while (node != null ) {
list.add(node.val);
node = node.next;
}
Collections.sort(list);
node = head;
int i = 0 ;
while (node != null ) {
node.val = list.get(i);
node = node.next;
i++;
}
return head;
}
}
思路解析
必会知识
23. 合并 K 个升序链表 请你将所有链表合并到一个升序链表中，返回合并后的链表。
具体题解 class Solution {
public ListNode mergeKLists (ListNode[] lists) {
if (lists == null ) return null ;
Queue<ListNode> queue = new PriorityQueue <>(new Comparator <ListNode>() {
@Override
public int compare (ListNode x, ListNode y) {
return x.val - y.val;
}
});
ListNode dummy = new ListNode (0 );
ListNode dummy1 = dummy;
for (ListNode node : lists) {
if (node != null ) {
queue.offer(node);
}
}
while (!queue.isEmpty()) {
dummy.next = queue.poll();
dummy = dummy.next;
if (dummy.next != null ) {
queue.offer(dummy.next);
}
}
return dummy1.next;
}
}
思路解析 利用最小堆内部排序算法来排序链表。每次取出的链表节点都是当前最小的，将该节点接入 dummy 后，再把剩余节点加入堆中重新排序。这里注意某链表为 null 则不加入最小堆中。
必会知识 Queue<ListNode> queue = new PriorityQueue <>(new Comparator <ListNode>() {
@Override
public int compare (ListNode x, ListNode y) {
return x.value - y.value;
}
});
146. LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
具体题解 class LRUCache {
class DlinkNode {
int key;
int value;
DlinkNode next;
DlinkNode prev;
public DlinkNode () {}
public DlinkNode (int key1, int value1) {
key = key1;
value = value1;
}
}
private int size;
private int capacity;
private Map<Integer, DlinkNode> map;
private DlinkNode dummyhead = new DlinkNode ();
private DlinkNode dummytail = new DlinkNode ();
public LRUCache (int capacity) {
this .size = 0 ;
this .capacity = capacity;
map = new HashMap <>();
dummyhead.next = dummytail;
dummytail.prev = dummyhead;
}
public int get (int key) {
if (!map.containsKey(key)) {
return -1 ;
}
moveToHead(map.get(key));
return map.get(key).value;
}
public void put (int key, int value) {
if (map.containsKey(key)) {
map.get(key).value = value;
moveToHead(map.get(key));
} else {
DlinkNode tmp = new DlinkNode (key, value);
addToHead(tmp);
map.put(key, tmp);
size++;
if (size > capacity) {
removeTail();
size--;
}
}
}
private void moveToHead (DlinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
addToHead(node);
}
private void addToHead (DlinkNode node) {
DlinkNode tmp = dummyhead.next;
node.prev = dummyhead;
node.next = dummyhead.next;
dummyhead.next = node;
tmp.prev = node;
}
private void removeTail () {
DlinkNode tmp = dummytail.prev;
dummytail.prev = tmp.prev;
tmp.prev.next = dummytail;
map.remove(tmp.key);
}
}
思路解析 这里存储 key，value，因此主要使用 Map 数据结构存储，链表来维护 LRU 队列。链表中的 key 用来与 map 映射，方便 map.move(tmp.key)。链表中的 value 用来存储值。需要实现链表头与链表尾方便定位，实现 moveToHead，addToHead，removeTail 函数。
必会知识 
