141. 环形链表
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {// 思路：使用哈希表，遍历链表并将节点存入哈希表// 如果遇到相同的节点，说明链表中有环// 初始化当前节点为链表的头节点ListNode cur = head;// 创建一个哈希集合用于存储已经访问过的节点Set<ListNode> set = new HashSet<>();// 逐个遍历链表while(cur != null) {// 将当前节点的下一个节点保存在临时变量中ListNode next = cur.next;// 如果下一个节点已经存在于哈希集合中，则说明有环if (set.contains(next)) {// 发现环，返回truereturn true;}// 将当前节点的下一个节点加入哈希集合set.add(next);// 移动当前节点到下一个节点cur = next;}// 遍历完链表没有发现环，返回falsereturn false;}}
2. 两数相加
/*** Definition for singly-linked list.* 定义单链表节点* public class ListNode {int val; // 节点的值ListNode next; // 指向下一个节点的指针ListNode() {} // 默认构造函数ListNode(int val) { this.val = val; } // 带值的构造函数ListNode(int val, ListNode next) { this.val = val; this.next = next; } // 带值和下一个节点的构造函数
}**/class Solution {// addTwoNumbers 方法用于将两个链表表示的数字相加public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 创建一个哨兵节点，方便后续获取结果及遍历ListNode pre = new ListNode(0);// 定义指针 cur 指向当前节点，初始指向哨兵节点ListNode cur = pre;// 初始化进位值，范围在 0-1int carry = 0;// 遍历两个链表，直到它们都为空while (l1 != null || l2 != null) {// 如果链表 l1 非空，则取其值；否则用 0 代替int x = l1 == null ? 0 : l1.val;// 如果链表 l2 非空，则取其值；否则用 0 代替int y = l2 == null ? 0 : l2.val;// 计算当前位的和：两个节点的值加上进位int sum = x + y + carry;// 更新进位值carry = sum / 10; // 计算新的进位// 计算当前节点的实际值（个位）sum = sum % 10; // 取当前和的个位数// 创建新的节点，将其添加到结果链表中cur.next = new ListNode(sum);// 移动 cur 指针到下一个节点cur = cur.next;// 移动 l1 指针到下一个节点if (l1 != null) {l1 = l1.next;}// 移动 l2 指针到下一个节点if (l2 != null) {l2 = l2.next;}}// 如果最后还有进位，创建一个新节点，将其添加到结果链表的末尾if (carry > 0) {cur.next = new ListNode(carry);}// 返回哨兵节点的下一个节点，即为结果链表的头节点return pre.next;}
}
21. 合并两个有序链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {/*** 合并两个有序链表* @param l1 第一个有序链表* @param l2 第二个有序链表* @return 合并后的有序链表*/public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 创建一个虚拟头节点，值为 -1ListNode preHead = new ListNode(-1);// prev 用于遍历合并后的链表ListNode prev = preHead;// 当 l1 和 l2 都不为空时while (l1 != null && l2 != null) {// 如果 l1 的值小于等于 l2 的值if (l1.val < l2.val) {// 将 l1 节点连接到合并后的链表中prev.next = l1;// l1 指向下一个节点l1 = l1.next;} else {// 将 l2 节点连接到合并后的链表中prev.next = l2;// l2 指向下一个节点l2 = l2.next;}// prev 指向下一个节点prev = prev.next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 == null ? l2 : l1;// 返回虚拟头节点的下一个节点，即合并后的链表头节点return preHead.next;}}
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 {// 方法 copyRandomList 接收链表头节点并返回深拷贝后的链表头节点public Node copyRandomList(Node head) {// 如果头节点为空，直接返回 nullif (head == null) {return null;}Node cur = head; // 定义当前指针，初始化为链表头// 定义哈希表，key 为旧的节点，value 为新的节点Map<Node, Node> map = new HashMap<>();// 第一次遍历，将旧链表的每个节点和对应的新节点存入哈希表while (cur != null) {// 创建新节点，并将其与旧节点的映射存入哈希表map.put(cur, new Node(cur.val));cur = cur.next; // 移动到下一个节点}cur = head; // 重置当前指针，指向链表头// 第二次遍历，构建新链表的 next 和 random 指向while (cur != null) {// 设置新节点的 next 指向对应的下一个节点// 使用哈希表获取新节点的引用map.get(cur).next = map.get(cur.next);// 设置新节点的 random 指向对应的随机节点map.get(cur).random = map.get(cur.random);cur = cur.next; // 移动到下一个节点}// 返回新链表的头节点，通过哈希表获取return map.get(head);}}
92. 反转链表 II
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 方法 reverseBetween 用于在链表中反转从位置 left 到 right 的节点public ListNode reverseBetween(ListNode head, int left, int right) {// 创建一个虚拟头节点（dummyNode），为处理边界情况提供便利ListNode dummyNode = new ListNode(-1);dummyNode.next = head; // 将虚拟节点指向原链表的头ListNode pre = dummyNode; // pre 指针初始化为虚拟头节点// 找到位置 left 的前一个节点for (int i = 0; i < left - 1; i++) {pre = pre.next; // 移动 pre 指针}// cur 指向要反转的第一个节点ListNode cur = pre.next;ListNode next; // 用于保存下一个节点// 开始反转从 left 到 right 的节点for (int i = 0; i < right - left; i++) {next = cur.next; // 暂存 cur 的下一个节点cur.next = next.next; // 弹出 next 节点next.next = pre.next; // 将 next 插入到 pre 指针的后面pre.next = next; // 更新 pre 的 next 指向插入后的节点}// 返回新链表的头节点return dummyNode.next;}
}
19. 删除链表的倒数第 N 个结点
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 1. 定义一个哨兵节点，哨兵节点的 next 指向链表头ListNode dummy = new ListNode(0, head);// 2. 定义一个双端队列，用于存储链表的节点Deque<ListNode> stack = new LinkedList<>();// 3. 创建一个指针 cur 从哨兵节点开始遍历链表ListNode cur = dummy;// 4. 将所有的节点遍历并入栈while (cur != null) {stack.push(cur); // 将当前节点压入栈中cur = cur.next; // 移动到下一个节点}// 5. 出栈 n 次，找到倒数第 n 个节点的前一个节点for (int i = 0; i < n; i++) {stack.pop(); // 弹出栈顶节点}// 6. peek 获取当前栈顶元素，即倒数第 n 个节点的前一个节点ListNode pre = stack.peek(); // 7. 将 pre 的 next 指向下下一个节点，跳过要删除的节点pre.next = pre.next.next;// 8. 返回哨兵节点的后续节点，这即是新的链表头return dummy.next; }
}
82. 删除排序链表中的重复元素 II
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 删除排序链表中的重复元素public ListNode deleteDuplicates(ListNode head) {// 1. 如果链表为空，直接返回if (head == null) {return head;}// 2. 创建一个哨兵节点，指向链表头ListNode dummy = new ListNode(0, head);ListNode cur = dummy; // 当前指针，初始化为哨兵节点// 3. 遍历链表while (cur.next != null && cur.next.next != null) {// 如果当前节点的值与下一个节点的值相同if (cur.next.val == cur.next.next.val) {int x = cur.next.val; // 记录重复的值// 4. 跳过所有与该值相同的节点while (cur.next != null && cur.next.val == x) {cur.next = cur.next.next; // 删除当前节点}} else {// 5. 移动到下一个节点cur = cur.next;}}// 6. 返回去掉重复节点后链表的头节点return dummy.next; // 返回哨兵节点的下一个节点作为新头}
}
61. 旋转链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 将链表向右旋转 k 个位置public ListNode rotateRight(ListNode head, int k) {// 1. 如果 k 为 0，链表为空或者只有一个节点，则直接返回头节点if (k == 0 || head == null || head.next == null) {return head;}// 2. 统计链表的长度 nint n = 1; // 初始化长度为 1，包含头节点ListNode iter = head; // 用于遍历链表while (iter.next != null) {iter = iter.next; // 移动到下一个节点n++; // 长度加 1}// 3. 计算需要连接的位置int add = n - k % n; // 计算新的头节点的位置if (add == n) {return head; // 如果 add 等于 n，表示不需要旋转，直接返回头节点}// 4. 创建环形链表iter.next = head; // 连接链表尾到头节点，形成环// 5. 找到新的尾节点while (add-- > 0) {iter = iter.next; // 移动到新的尾节点}// 6. 断开环并返回新头节点ListNode ret = iter.next; // 新头节点iter.next = null; // 断开连接return ret; // 返回新头节点}
}
86. 分隔链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode partition(ListNode head, int x) {// 创建一个新节点 small，作为小于 x 的链表的头节点ListNode small = new ListNode(0);// 记录小于 x 的链表的头节点，方便最后返回ListNode smallHead = small;// 创建一个新节点 large，作为大于等于 x 的链表的头节点ListNode large = new ListNode(0);// 记录大于等于 x 的链表的头节点，方便最后连接ListNode largeHead = large;// 遍历原始链表while (head!= null) {if (head.val < x) {// 如果当前节点值小于 x，将其加入到 small 链表中small.next = head;small = small.next;} else {// 如果当前节点值大于等于 x，将其加入到 large 链表中large.next = head;large = large.next;}// 移动原始链表的指针head = head.next;}// 将 large 链表的末尾置为 null，防止出现循环引用large.next = null;// 将 small 链表和 large 链表连接起来small.next = largeHead.next;// 返回划分后的链表的头节点return smallHead.next;}
}
146. LRU 缓存
class LRUCache {// 定义双向链表class DLinkedNode {// 存储map的keyint key;// 存储valueint value;// 前驱指针DLinkedNode prev;// 后继指针DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int key, int value) {this.key = key;this.value = value;}}// 链表长度private int size;// 链表容量private int capacity;// 定义头节点private DLinkedNode head;// 定义尾节点private DLinkedNode tail;// 定义哈希表key为key，value为双向链表Map<Integer, DLinkedNode> cache = new HashMap<>();public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}// 获取值并将节点移到头部标识刚使用过public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}moveToHead(node);return node.value;}// 移动刚使用的节点到头部public void moveToHead(DLinkedNode node) {// 将node移除下来removeNode(node);// 将Node节点加到Head位置addToHead(node);}// 将Node节点加到Head位置private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}// 将node移除下来private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}// 移除尾部节点public DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的相cache.remove(tail.key);--size;} } else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
