链表
2025年6月14日大约 16 分钟
链表
两个链表的交点 - LeetCode 160
- 两个链表相交，则相交点之后的节点都是相同的
- A 走完走 B，B 走完走 A，步数一样就会相遇。
- 举例：
A 长度 = 3 (a1 → a2 → c1 → c2 → c3)
B 长度 = 4 (b1 → b2 → b3 → c1 → c2 → c3)
pA: a1 → a2 → c1 → c2 → c3 → null → b1 → b2 → b3 → c1 ←★
pB: b1 → b2 → b3 → c1 → c2 → c3 → null → a1 → a2 → c1 ←★
最后pA和pB都走了9步，在c1相遇, 因为c1是相交点public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
p1 = p1 == null ? headB : p1.next; // 如果p1走到头，则从headB开始
p2 = p2 == null ? headA : p2.next; // 如果p2走到头，则从headA开始
}
return p1; // 返回p1或p2都可以，因为p1和p2相遇时，就是相交点
}回文链表 - LeetCode 234
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 1. 快慢指针找中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
}
// 2. 反转后半部分
ListNode prev = null, curr = slow.next; // slow.next 是后半部分的头节点
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 3. 比较前后两段
ListNode p1 = head, p2 = prev; // prev 是反转后的后半部分的头节点，p1是前半部分的头节点
while (p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}环形链表 - LeetCode 141
- 快慢指针
- 快指针每次走两步，慢指针每次走一步
- 如果链表有环，则快慢指针一定会相遇
- 如果链表没有环，则快指针会走到链表末尾
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) { // 如果快指针走到链表末尾，则链表没有环
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}环形链表II - LeetCode 142
- 快慢指针 返回环的入口节点
- 有环时，快慢指针相遇后，设置两个指针，一个指针从头部开始，一个指针从相遇点开始，每次走一步，直到相遇，相遇点即为环入口
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {// 有环
ListNode index1 = fast;
ListNode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}两数相加 - LeetCode 2
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 虚拟头节点
ListNode curr = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int x = (l1 != null) ? l1.val : 0; // 如果l1不为空，则取l1的值，否则取0
int y = (l2 != null) ? l2.val : 0; // 如果l2不为空，则取l2的值，否则取0
int sum = x + y + carry; // 计算当前位的和
carry = sum / 10; // 计算进位
curr.next = new ListNode(sum % 10); // 创建真正的第一个节点，值为sum的个位数
curr = curr.next;
if (l1 != null) l1 = l1.next; // 如果l1不为空，则移动到下一个节点
if (l2 != null) l2 = l2.next; // 如果l2不为空，则移动到下一个节点
}
// 最后一位如果还有进位
if (carry > 0) { // 如果进位大于0，则创建新节点，值为进位
curr.next = new ListNode(carry);
}
return dummy.next; // 返回虚拟头节点的下一个节点，即结果链表的头节点
}合并两个有序链表 - LeetCode 21
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val> list2.val){ // 如果list1的值大于list2的值
list2.next = mergeTwoLists(list1,list2.next); // 递归调用，将list1和list2的下一个节点合并
return list2; // 返回小的因为构建链表时，小的在前面
}else{ // 如果list1的值小于等于list2的值
list1.next = mergeTwoLists(list1.next,list2); // 递归调用，将list1的下一个节点和list2合并
return list1;
}
}LRU 缓存 - LeetCode 146
- 使用双向链表和哈希表实现
- 双向链表用于存储缓存数据，哈希表用于快速查找数据
- 当缓存满时，删除双向链表的最后一个节点
- 当缓存未满时，将新数据插入双向链表的头部
- 当缓存命中时，将该数据移动到双向链表的头部
class LRUCache {
class Node {
int key, value; // Node 里面的 key 是冗余存储，用来辅助删除时从 HashMap 里移除对应项。
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private int capacity;
private Map<Integer, Node> map; // key是key value存储node
private Node head, tail; // 虚拟头尾节点
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0); // dummy head
tail = new Node(0, 0); // dummy tail
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1; // 如果缓存中没有该数据，则返回-1
Node node = map.get(key); // 获取该数据
moveToHead(node); // 将该数据移动到链表头部 (头部是最近使用的)
return node.value; // 返回该数据
}
public void put(int key, int value) {
if (map.containsKey(key)) { // 如果缓存中已经有该数据
Node node = map.get(key); // 获取该数据
node.value = value; // 更新该数据
moveToHead(node); // 将该数据移动到链表头部 (头部是最近使用的)
} else { // 如果缓存中没有该数据
if (map.size() == capacity) { // 如果缓存已满
Node lru = tail.prev; // 获取链表最后一个节点
remove(lru); // 删除该节点
map.remove(lru.key); // 从哈希表中删除该数据
}
//添加新节点 无论是否满
Node newNode = new Node(key, value); // 创建新节点
addToHead(newNode); // 将新节点添加到链表头部
map.put(key, newNode); // 将新节点添加到哈希表中
}
}
// 把节点移到链表头
private void moveToHead(Node node) {
remove(node);
addToHead(node);
}
// 从链表中删除节点node
private void remove(Node node) {
node.prev.next = node.next; // 让 node 前面的节点，直接指向 node 的下一个
node.next.prev = node.prev; // 让 node 后面的节点，直接指向 node 的前一个
}
// 添加节点到链表头
private void addToHead(Node node) {
node.next = head.next; //
head.next.prev = node;
head.next = node;
node.prev = head;
}
}随机链表的复制 - LeetCode 138
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
Map<Node,Node> cachedNoded = new HashMap<>(); // key是原节点 value是复制的新节点, map放在方法外因为 所有递归共享缓存
public Node copyRandomList(Node head) {
if(head == null) return null; // 如果头节点为空，则返回空
if(!cachedNoded.containsKey(head)){ // 如果缓存中没有该节点
Node headNew = new Node(head.val); // 创建新节点
cachedNoded.put(head,headNew); // 将新节点添加到缓存中
head.next = copyRandomList(head.next); // 递归复制next
head.random = copyRandomList(head.random); // 递归复制random
}
return cachedNoded.get(head);
}
}两两交换链表中的节点 - LeetCode 24
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0); // 虚拟头节点
dummy.next = head; // 虚拟头节点指向真的头节点
ListNode pre = dummy; // 前一个节点
while (head != null && head.next != null) { // 遍历链表
ListNode first = head; // 第一个节点
ListNode second = head.next; // 第二个节点
first.next = second.next; // 第一个节点指向第二个节点的下一个节点
second.next = first; // 第二个节点指向第一个节点
pre.next = second; // 前一个节点指向第二个节点
pre = first; // 移动到第一个节点
head = first.next; // 移动到下一个节点
}
return dummy.next;
}
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next; // 新的头节点
head.next = swapPairs(newHead.next); // 递归交换下一个节点
newHead.next = head; // 新的头节点指向当前节点
return newHead;
}反转链表 - LeetCode 206
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 前一个节点
ListNode curr = head; // 当前节点
while (curr != null) { // 遍历链表
ListNode next = curr.next; // 记录下一个节点
curr.next = prev; // 反转当前节点: 指针反向
// 移动到下一个节点
prev = curr;
curr = next;
}
return prev; // 返回前一个节点，即反转后的头节点
}反转链表II - LeetCode 92
- 在
[pre]之后，不断把cur.next（也就是下一个节点）插入到pre.next的位置，相当于：“把当前区间中的下一个节点，不断插到区间最前面”，从而完成原地逆转。
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0); // 虚拟头节点
dummy.next = head; // 虚拟头节点指向真的头节点
ListNode pre = dummy;
for (int i = 0; i < left - 1; i++) {
pre = pre.next; // 移动到left的前一个节点
}
ListNode cur = pre.next; // cur 是正在被“搬家”的节点
ListNode next;
for (int i = 0; i < right - left; i++) { // right - left 是搬家的次数
next = cur.next; // 记录下个节点
cur.next = next.next; // 断链，让 cur 指向下下个节点
next.next = pre.next; // 将 next 插入到 pre 后面
pre.next = next; // pre 重新指向 next
}
return dummy.next;
}K个一组翻转链表 - LeetCode 25
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0); // 虚拟头节点
dummy.next = head; // 虚拟头节点指向真的头节点
ListNode pre = dummy; // 前一个节点
while (head != null) { // 遍历链表
ListNode tail = pre; // 记录当前区间的尾节点
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; i++) {
tail = tail.next; // 移动到当前区间的尾节点
if (tail == null) { // 如果当前区间长度小于k，则不反转，直接返回
return dummy.next;
}
}
ListNode nex = tail.next; // 记录当前区间的下一个节点
ListNode[] reverse = myReverse(head, tail); // 反转当前区间
head = reverse[0]; // 更新当前区间的头节点
tail = reverse[1]; // 更新当前区间的尾节点
// 把子链表重新接回原链表
pre.next = head; // 将当前区间的头节点接回原链表
tail.next = nex; // 将当前区间的尾节点接回原链表
pre = tail; // 移动到当前区间的尾节点
head = tail.next; // 移动到当前区间的下一个节点
}
return dummy.next; // 返回虚拟头节点的下一个节点，即结果链表的头节点
}
public ListNode[] myReverse(ListNode head, ListNode tail) {
ListNode prev = tail.next; // 前一个节点
ListNode cur = head; // 当前节点
while (prev != tail) {
ListNode next = cur.next; // 下一个节点
cur.next = prev; // 反转当前节点
prev = cur; // 移动到当前节点
cur = next; // 移动到下一个节点
}
return new ListNode[]{tail, head};
}删除链表的倒数第N个节点 - LeetCode 19
- 让快指针先走n步，然后快慢指针一起走，当快指针走到链表末尾时，慢指针就指向了倒数第n个节点。
- second 指针起点是哑节点 dummy，在 head 之前。
- 这样做的原因是：当要删除的节点是链表的第一个节点时，second 还能停在 dummy，方便通过 second.next = second.next.next 删除头节点。
- 这样就避免了单独处理头节点的特殊情况，代码更简洁。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // 虚拟头节点
ListNode fast = head; // 快指针
ListNode slow = dummy; // 慢指针
for (int i = 0; i < n; i++) {
fast = fast.next; // 快指针走n步
}
while (fast != null) {
fast = fast.next; // 快指针走一步
slow = slow.next; // 慢指针走一步
}
slow.next = slow.next.next; // 删除倒数第n个节点
return dummy.next; // 返回虚拟头节点的下一个节点，即结果链表的头节点
}删除链表中的重复节点 - LeetCode 82
- 删除所有重复的，不保留
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0,head); // 虚拟头节点，指向真的头节点
ListNode prev = dummy;
while(head != null){ // 遍历链表
if(head.next != null && head.val == head.next.val){ // 如果当前节点和下一个节点值相同
while (head.next != null && head.val == head.next.val) { // 如果当前节点和下一个节点值相同
head = head.next; // 移动到下一个节点 直到不相同
}
prev.next = head.next; // 删除中间所有的重复节点
} else{ // 如果当前节点和下一个节点值不同
prev = prev.next; // 移动到下一个节点
}
head = head.next; // 移动到下一个节点
}
return dummy.next; // 返回虚拟头节点的下一个节点，即结果链表的头节点
}删除排序链表中的重复元素 - LeetCode 83
- 删除其他重复的，保留一个
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next; // 跳过重复节点
} else {
current = current.next; // 继续遍历
}
}
return head;
}旋转链表 - LeetCode 61
从头开始走 length - (k % length) 步，走到的节点就是新尾巴，它的 next 就是新头，然后断开它的 next。
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) return head;
int n = 1; // 链表长度
ListNode iter = head; // 遍历链表
// 计算链表长度
while (iter.next != null) { // 遍历链表
iter = iter.next; // 移动到下一个节点
n++; // 链表长度加1
}
// k % n 是“有效的右移步数”，因为右移 n 步相当于转了一圈回来了，所以取模
// 从头节点开始，往后走 n - k % n 步，走到的那个节点是新的尾巴，下一个节点，就是新的头节点。
// 举例：head = [1,2,3,4,5], k = 2
// 链表长度 n = 5
// k % n = 2 % 5 = 2
// n - k % n = 5 - 2 = 3
// 从头节点开始，往后走 3 步，走到的那个节点是新的尾巴，下一个节点，就是新的头节点。
// 新的尾巴是 3，新的头是 4
// 断开 3 和 4 之间的连接，返回 4
int add = n - k % n; // 计算需要移动的步数
if (add == n) return head; // 如果需要移动的步数等于链表长度，则直接返回
iter.next = head; // 将链表连接成环
while (add-- > 0) { // 移动到新的尾巴
iter = iter.next;
}
ListNode ret = iter.next; // 新的头
iter.next = null; // 断开环
return ret;
}分隔链表 - LeetCode 86
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0); // 存放小于x的节点
ListNode smallHead = small; // 小链表的头节点
ListNode large = new ListNode(0); // 存放大于等于x的节点
ListNode largeHead = large; // 大链表的头节点
while (head != null) {
if (head.val < x) {
small.next = head; // 将当前节点添加到小链表
small = small.next; // 移动到小链表的下一个节点
} else {
large.next = head; // 将当前节点添加到大链表
large = large.next; // 移动到大链表的下一个节点
}
head = head.next; // 移动到下一个节点
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}排序链表 - LeetCode 148
- 归并排序是一种 分治 算法，将链表不断一分为二，排序后再合并两个有序链表
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 1. 使用快慢指针找到中间节点
ListNode slow = head, fast = head, pre = null;
while (fast != null && fast.next != null) {
pre = slow; // 记录slow慢指针的前一个节点，用来断开链表
slow = slow.next;
fast = fast.next.next;
} // 快指针走到链表末尾时，慢指针走到链表中间
pre.next = null; // 断开链表是为了把链表一分为二，递归处理左右部分，这是归并排序中“分”的关键。
// 2. 递归排序左右部分
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// 3. 合并两个有序链表
return merge(l1, l2);
}
// 合并两个有序链表
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
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;
}
cur.next = (l1 != null) ? l1 : l2; // 如果l1不为空，则将l1赋给cur的下一个节点，否则将l2赋给cur的下一个节点
return dummy.next;
}
}合并K个升序链表 - LeetCode 23
- 分治递归地两两合并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1); // 参数：
// 1. 链表数组 lists
// 2. 左边界 l
// 3. 右边界 r
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) { // 终止条件：如果左边界等于右边界，则返回链表
return lists[l];
}
if (l > r) { // 终止条件：如果左边界大于右边界，则返回空
return null;
}
int mid = (l + r)/2; // 中间位置
// merge(lists, l, mid)：递归处理左边一半的链表，最终返回一个合并后的链表。
// merge(lists, mid+1, r)：递归处理右边一半的链表，也返回一个合并后的链表。
// mergeTwoLists(...)：将左右两个合并好的链表，再合并为一个大链表返回。
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); // 递归合并两个链表
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b; // 如果a不为空，则返回a，否则返回b
}
ListNode dummy = new ListNode(0); // 虚拟头节点
ListNode tail = dummy, aPtr = a, bPtr = b; // 临时节点
while (aPtr != null && bPtr != null) { // 合并两个链表
if (aPtr.val < bPtr.val) { // 如果a的值小于b的值
tail.next = aPtr; // 将a的值赋给tail的下一个节点
aPtr = aPtr.next; // 移动到a的下一个节点
} else { // 如果a的值大于等于b的值
tail.next = bPtr; // 将b的值赋给tail的下一个节点
bPtr = bPtr.next; // 移动到b的下一个节点
}
tail = tail.next; // 移动到tail的下一个节点
}
tail.next = (aPtr != null ? aPtr : bPtr); // 如果a不为空，则将a赋给tail的下一个节点，否则将b赋给tail的下一个节点
return dummy.next; // 返回虚拟头节点的下一个节点，即结果链表的头节点
}
}设计链表 - LeetCode 707
//单链表
class MyLinkedList {
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val=val;
}
}
//size存储链表元素的个数
private int size;
//注意这里记录的是虚拟头结点
private ListNode head;
//初始化链表
public MyLinkedList() {
this.size = 0;
this.head = new ListNode(0);
}
//获取第index个节点的数值，注意index是从0开始的，第0个节点就是虚拟头结点
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
//第0个节点是虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
size++;
// 在链表最前面插入一个节点，等价于在第0个元素前添加
// addAtIndex(0, val);
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
size++;
// 在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
// addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
//找到要插入节点的前驱
ListNode pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
//因为有虚拟头节点，所以不用对index=0的情况进行特殊处理
ListNode pre = head;
for (int i = 0; i < index ; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
}