1 相交链表
先遍历两个链表，统计各自长度。
让长的链表先走diff步
再往后各走一步，直到两个链表相交，或者是走到了末尾(null)。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA, curB = headB; int lenA = 0; int lenB = 0; while (curA != null) { curA = curA.next; lenA++; } while (curB != null) { curB = curB.next; lenB++; } int diff = Math.abs(lenA - lenB); curA = headA; curB = headB; if (lenA > lenB) { while (diff > 0) { curA = curA.next; diff--; } } else { while (diff > 0) { curB = curB.next; diff--; } } while (curA != null && curB != null && curA != curB) { curA = curA.next; curB = curB.next; } return curA; } }2 翻转链表
令pre == null， cur = head，temp保存cur的next节点。
迭代遍历，改变cur的指向即可。
最后退出循环的条件是cur == null，此时pre指向新的链表头
返回pre即可。
/** * 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 reverseList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre= cur; cur = temp; } return pre; } }3 回文链表
先找中点，翻转后半部分链表。最后一一比较前半部分链表和后半部分链表节点的值，如果不相同返回flase;退出循环了返回true;
找中点的时候有点不舒服，考虑奇偶，反正最后的slow指向奇数的中点，偶数的前半部分最后一个。
细心一点不会出错的。
/** * 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 boolean isPalindrome(ListNode head) { if(head == null || head.next == null) { return true; } ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } ListNode newHead = reverse(slow.next); ListNode curLeft = head; ListNode curRight = newHead; while (curRight != null) { if (curLeft.val != curRight.val) { return false; } curLeft = curLeft.next; curRight = curRight.next; } return true; } public ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }4 环形链表
快慢指针，fast走两步，slow走三步。如果相遇则返回true,否则false;
/** * 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) { if(head == null || head.next == null) { return false; } ListNode fast = head, slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(slow == fast) { return true; } } return false; } }5 环形链表Ⅱ
先快慢指针判断有没有环，用一个布尔变量haveCircle来表示。
没有环则返回null；
有环，令slow = head，快慢指针以相同速度遍历，相遇的地方就是入口。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head, slow = head; boolean haveCircle = false; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { haveCircle = true; break; } } if (!haveCircle) { return null; } slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } }6 合并两个升序链表
虚拟头节点dummy
while条件cur1 != null && cur2 != null
最后把剩下的拼到cur后面即可。
返回dummy.next;
/** * 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 mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0, null); ListNode cur = dummy; ListNode cur1 = list1, cur2 = list2; while (cur1 != null && cur2 != null) { if (cur1.val < cur2.val) { cur.next = cur1; cur1 = cur1.next; cur = cur.next; } else { cur.next = cur2; cur2 = cur2.next; cur = cur.next; } } cur.next = cur1 == null ? cur2 : cur1; return dummy.next; } }7 两数相加
定义四个变量：value、carry、val1、val2
while循环的进入条件是cur1 != null || cur2 != null
每次先计算val1、val2，若为空则是0，否则是节点的值。
然后计算value和进位carry
然后创建新节点。
最后判断cur1、cur2需不需要指向下一位，如果是null则不能执行cur1.next，否则会空指针异常
/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; int carry = 0, value = 0; int val1 = 0, val2 = 0; ListNode cur1 = l1, cur2 = l2; while (cur1 != null || cur2 != null) { val1 = cur1 == null ? 0 : cur1.val; val2 = cur2 == null ? 0 : cur2.val; value = (val1 + val2 + carry) % 10; carry = (val1 + val2 + carry) / 10; cur.next = new ListNode(value); cur = cur.next; if (cur1 != null) cur1 = cur1.next; if (cur2 != null) cur2 = cur2.next; } if(carry == 1) { cur.next = new ListNode(1); } return dummy.next; } }8 删除倒数第N个节点
快慢指针
快指针从虚拟头节点开始先走n步
然后快慢指针同时走，直到fast.next == null;
这个时候slow指向要删除节点的前一个节点
改变slow节点的指向即可。
/** * 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) { ListNode dummy = new ListNode(-1, head); ListNode fast = dummy, slow = dummy; while (n > 0) { fast = fast.next; n--; } while (fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next; } }9 两两交换链表中的节点
感觉还是有点不熟练
虚拟头节点dummy
cur = dummy
while条件cur.next != null && cur.next.next != null，要保证后面有两个可以交换的节点。
temp = node2.next;
cur.next = node2;
node2.next = node1;
node1.next = temp;
cur = node1;
/** * 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 swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(-1, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { ListNode node1 = cur.next; ListNode node2 = cur.next.next; ListNode temp = node2.next; cur.next = node2; node2.next = node1; node1.next = temp; cur = node1; } return dummy.next; } }10 K个一组翻转链表（难）
虚拟头节点（dummy）：避免单独处理第一组翻转后的头节点，统一拼接逻辑；
分组定位：用 end 指针找到每组的尾节点（每组包含 k 个节点），若剩余节点不足 k 个则终止；
局部翻转：断开当前组与后续链表的连接，翻转当前 k 个节点；
链表拼接：将翻转后的本组链表与前一组、后一组重新拼接；
指针重置：更新指针位置，处理下一组节点。
/** * 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 reverseKGroup(ListNode head, int k) { // 1. 虚拟头节点：值为-1，next指向原链表头，简化头节点处理 ListNode dummy = new ListNode(-1, head); // pre：上一组的尾节点（初始为虚拟头，用于拼接当前组） ListNode pre = dummy; // end：当前组的尾节点（初始为虚拟头，用于定位每组的边界） ListNode end = dummy; // 循环处理每一组，直到end的下一个节点为空（无更多节点） while (end.next != null) { // 2. 定位当前组的尾节点：移动k次，找到第k个节点 for (int i = 0; i < k && end != null; i++) { end = end.next; // 每次后移一位，最终end指向当前组最后一个节点 } // 如果end为null，说明剩余节点不足k个，直接终止循环（保留原顺序） if (end == null) break; // 3. 记录关键节点，为翻转和拼接做准备 ListNode start = pre.next; // 当前组的头节点（翻转前） ListNode nextHead = end.next; // 下一组的头节点（当前组尾的下一个） end.next = null; // 断开当前组与下一组的连接，避免翻转时影响后续节点 // 4. 翻转当前组，并将翻转后的链表拼接到pre之后 pre.next = reverse(start); // 翻转后start变为当前组尾，新头是原end，pre.next指向新头 start.next = nextHead; // 原start（当前组尾）连接下一组的头，恢复链表连续性 // 5. 重置指针，处理下一组 pre = start; // pre移动到当前组的尾（原start），作为下一组的pre end = pre; // end从pre重新开始，定位下一组的尾节点 } // 虚拟头的next就是翻转后的链表头 return dummy.next; } // 辅助方法：翻转以head为头的单链表，返回翻转后的头节点（原链表的尾） public ListNode reverse(ListNode head) { ListNode pre = null; // 前一个节点（初始为null，翻转后是新链表的尾） ListNode cur = head; // 当前节点（初始为原链表头） // 迭代翻转每个节点的next指向 while (cur != null) { ListNode temp = cur.next; // 临时保存当前节点的下一个节点（避免丢失） cur.next = pre; // 翻转：当前节点指向pre（原前一个节点） pre = cur; // pre后移，变为当前节点 cur = temp; // cur后移，变为临时保存的下一个节点 } // 循环结束后，pre是翻转后的链表头（原链表的尾） return pre; } }11 随机链表的复制
第一次遍历原链表
用HashMap<Node, Node>存储原节点和copy节点
第二次遍历给copy节点next、random赋值
/* // 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 { public Node copyRandomList(Node head) { Node cur = head; HashMap<Node, Node> map = new HashMap<>(); while (cur != null) { Node copy = new Node(cur.val); map.put(cur,copy); 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); } }12 排序链表
写两个工具函数：
找中点(偶数时找左中点)；
排序两个有序链表
找到中点，找到rightHead = mid.next;
把mid.next = null，这一步是为了断开两个链表
拆成两个子链表，递归调用sortList(leftHead)、sortList(rightHead);
最后merge(left, right);
class Solution { public ListNode sortList(ListNode head) { // 递归终止条件：空链表 或 只有一个节点（无需排序） if (head == null || head.next == null) { return head; } // ========== 第一步：找中点，拆分链表 ========== // 找中点（左中点）：比如 1→2→3→4，中点是2；1→2→3，中点是2 ListNode midNode = findMid(head); // 右子链表的头节点 = 中点的下一个节点 ListNode rightListHead = midNode.next; // 拆分：将中点的next置为null，左链表为 head→midNode，右链表为 rightListHead→末尾 midNode.next = null; // ========== 第二步：递归排序左右子链表 ========== ListNode sortedLeft = sortList(head); // 排序左链表 ListNode sortedRight = sortList(rightListHead); // 排序右链表 // ========== 第三步：合并两个有序链表 ========== return merge(sortedLeft, sortedRight); } /** * 快慢指针找链表中点（关键：快指针初始为head.next，保证找左中点） * 原因：若快指针初始为head，偶数节点时会找右中点，拆分时可能死循环（如链表只有2个节点） */ private ListNode findMid(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; // 慢指针：初始头节点，每次走1步 ListNode fast = head.next; // 快指针：初始头节点的下一个，每次走2步 // 快指针没到末尾时，继续移动 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; // 慢指针最终指向左中点 } /** * 合并两个有序链表（经典操作，必须掌握） * @param l1 有序链表1 * @param l2 有序链表2 * @return 合并后的有序链表头 */ 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; // l1后移 } else { cur.next = l2; l2 = l2.next; // l2后移 } cur = cur.next; // 合并指针后移 } // 拼接剩余节点（其中一个链表可能已遍历完，另一个还有剩余） cur.next = l1 != null ? l1 : l2; // 虚拟头的next就是合并后的链表头 return dummy.next; } }13 合并k个升序链表
第一步：写一个合并2个升序链表的工具函数：mergeTwoLists(ListNode l1, ListNode l2);
第二步：写一个merge(Lists[] lists, int left, int right)函数：
找中点mid
leftHead = merge(lists, left, mid);
rightHead = merge(lists, mid + 1, right);
最后return mergeTwoLists(leftHead, rightHead)即可
第三步，在主函数中调用merge()函数即可。
/** * 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 mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) { return null; } return merge(lists,0, lists.length - 1); } public ListNode merge(ListNode[] lists ,int left, int right) { if(left == right) { return lists[left]; } int mid = left + (right - left) / 2; ListNode leftHead = merge(lists, left, mid); ListNode rightHead = merge(lists, mid + 1, right); return mergeTwoLists(leftHead, rightHead); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1, null); 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 ? l2 : l1; return dummy.next; } }14 LRU缓存
写两个工具函数addToHead()、removeNode()，减少代码量
关键的核心就是Map的key存Node节点的key，value存Node。Node节点里存储key、value、next、pre四个字段。get和put操作都需要根据key查找对应节点，找到其前驱和后继节点，修改指针。否则需要遍历，无法在O（1）的时间内完成。
class LRUCache { class Node{ int key; int value; Node next; Node pre; public Node(int key, int value, Node next, Node pre) { this.key = key; this.value = value; this.next = next; this.pre = pre; } } private int maxSize; private int curSize; private Node head; private Node tail; private HashMap<Integer, Node> map; public LRUCache(int capacity) { maxSize = capacity; curSize = 0; head = new Node(-1, -1, null, null); tail = new Node(-1, -1, null, null); head.next = tail; tail.pre = head; map = new HashMap<>(); } public int get(int key) { if(map.containsKey(key)) { Node cur = map.get(key); removeNode(cur); addToHead(cur); return cur.value; }else { return -1; } } public void put(int key, int value) { if(map.containsKey(key)) { Node cur = map.get(key); cur.value = value; removeNode(cur); addToHead(cur); }else{ Node cur = new Node(key, value, null, null); if(curSize < maxSize) { map.put(key, cur); addToHead(cur); curSize++; }else{ Node del = tail.pre; removeNode(del); map.remove(del.key); curSize--; map.put(key, cur); addToHead(cur); curSize++; } } } private void removeNode(Node node) { Node prev = node.pre; Node next = node.next; prev.next = next; next.pre = prev; // 清空节点指针，避免内存泄漏 node.pre = null; node.next = null; } private void addToHead(Node node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = 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); */如果要实现带TTL版本的思路：Node新增一个字段expireTime;
在构造函数里初始化expireTime = System.currentTimeMillis() + TTL,作为参数传入
每次get的时候判断System.currentTimeMillis() > expireTime，过期了就清除。
