摘要本文聚焦LeetCode热题100链表板块解析高频考点与经典解法。链表基础单向链表class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } public class SinglyLinkedList implements IterableInteger { private ListNode head; // 1. 头部添加 public void addFirst(int value) { ListNode newNode new ListNode(value); newNode.next this.head; this.head newNode; } // 2. 遍历相关 public void loopWhile(ConsumerInteger consumer) { ListNode curr this.head; while (curr ! null) { consumer.accept(curr.val); curr curr.next; } } public void loopFor(ConsumerInteger consumer) { for (ListNode curr this.head; curr ! null; curr curr.next) { consumer.accept(curr.val); } } private class NodeIterator implements IteratorInteger { ListNode curr head; Override public boolean hasNext() { return curr ! null; } Override public Integer next() { int value curr.val; curr curr.next; return value; } } Override public IteratorInteger iterator() { return new NodeIterator(); } public void loopRecursion() { recursion(this.head); } private void recursion(ListNode curr) { if (curr null) { return; } System.out.print(curr.val ); recursion(curr.next); } // 3. 尾部添加 private ListNode findLast() { if (this.head null) { return null; } ListNode curr; for (curr this.head; curr.next ! null; ) { curr curr.next; } return curr; } public void addLast(int value) { ListNode last findLast(); if (last null) { addFirst(value); return; } ListNode newNode new ListNode(value); last.next newNode; } public void addLast(int first, int... rest) { ListNode sublist new ListNode(first); ListNode curr sublist; for (int value : rest) { ListNode newNode new ListNode(value); curr.next newNode; curr curr.next; } ListNode last findLast(); if (last null) { this.head sublist; return; } last.next sublist; } // 4. 根据索引操作 private ListNode findNode(int index) { int i 0; for (ListNode curr this.head; curr ! null; curr curr.next, i) { if (index i) { return curr; } } return null; } private IllegalArgumentException illegalIndex(int index) { return new IllegalArgumentException(String.format(index [%d] 不合法, index)); } public int get(int index) { ListNode node findNode(index); if (node ! null) { return node.val; } throw illegalIndex(index); } // 5. 插入节点 public void insert(int index, int value) { if (index 0) { addFirst(value); return; } ListNode prev findNode(index - 1); if (prev null) { throw illegalIndex(index); } ListNode newNode new ListNode(value); newNode.next prev.next; prev.next newNode; } // 6. 删除节点 public void remove(int index) { if (index 0) { if (this.head ! null) { this.head this.head.next; return; } else { throw illegalIndex(index); } } ListNode prev findNode(index - 1); ListNode curr; if (prev ! null (curr prev.next) ! null) { prev.next curr.next; } else { throw illegalIndex(index); } } }虚拟头结点链表内还有一种特殊的节点称为哨兵Sentinel节点也叫做哑元 Dummy节点它不存储数据通常用作头尾用来简化边界判断。单向链表带哨兵class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } } public class SinglyLinkedListSentinel implements IterableInteger { private ListNode head new ListNode(0); private ListNode findNode(int index) { int i -1; for (ListNode curr this.head; curr ! null; curr curr.next, i) { if (i index) { return curr; } } return null; } //查找最后一个节点 private ListNode findLast() { ListNode curr; for (curr this.head; curr.next ! null; ) { curr curr.next; } return curr; } private IllegalArgumentException illegalIndex(int index) { return new IllegalArgumentException(String.format(索引 [%d] 不合法, index)); } //头部添加节点 public void addFirst(int value) { ListNode newNode new ListNode(value); newNode.next this.head.next; this.head.next newNode; } //尾部添加节点 public void addLast(int value) { ListNode last findLast(); ListNode newNode new ListNode(value); last.next newNode; } //尾部添加多个节点 public void addLast(int first, int... rest) { ListNode sublist new ListNode(first); ListNode curr sublist; for (int value : rest) { ListNode newNode new ListNode(value); curr.next newNode; curr curr.next; } ListNode last findLast(); last.next sublist; } //指定索引插入节点 public void insert(int index, int value) { ListNode prev findNode(index - 1); // index0 时prev 是哨兵节点 if (prev ! null) { ListNode newNode new ListNode(value); newNode.next prev.next; prev.next newNode; } else { throw illegalIndex(index); } } //指定索引删除节点 public void remove(int index) { ListNode prev findNode(index - 1); ListNode curr; if (prev ! null (curr prev.next) ! null) { prev.next curr.next; } else { throw illegalIndex(index); } } //根据索引获取节点值 public int get(int index) { ListNode node findNode(index); if (node ! null) { return node.val; } throw illegalIndex(index); } //while 遍历 public void loopWhile(ConsumerInteger consumer) { ListNode curr this.head.next; while (curr ! null) { consumer.accept(curr.val); curr curr.next; } } //for 遍历 public void loopFor(ConsumerInteger consumer) { for (ListNode curr this.head.next; curr ! null; curr curr.next) { consumer.accept(curr.val); } } //迭代器遍历 private class NodeIterator implements IteratorInteger { ListNode curr head.next; Override public boolean hasNext() { return curr ! null; } Override public Integer next() { int value curr.val; curr curr.next; return value; } } Override public IteratorInteger iterator() { return new NodeIterator(); } //递归遍历 public void loopRecursion() { recursion(this.head.next); } private void recursion(ListNode curr) { if (curr null) { return; } System.out.print(curr.val ); recursion(curr.next); } }160 相交链表核心逻辑通过 双指针边界对齐法 让两个指针遍历两个链表 —— 利用「指针遍历完自身链表后切换到另一链表头部」的特性每次遍历可消除两个链表的长度差逐步对齐指针的遍历边界无需额外空间且时间复杂度最优高效找到相交节点。关键步骤边界初始化定义两个指针分别指向两个链表头部nodeAheadAnodeBheadB边界对齐遍历循环判断 nodeA ! nodeB未相遇通过切换指针遍历路径对齐边界若 nodeA 遍历到自身链表末尾nodeA null切换到另一链表头nodeAheadB消除长度差若 nodeA 未到末尾继续遍历自身链表nodeAnodeA.next若 nodeB 遍历到自身链表末尾nodeB null切换到另一链表头nodeBheadA消除长度差若 nodeB 未到末尾继续遍历自身链表nodeBnodeB.next终止返回当循环因 nodeA nodeB 终止时返回该节点要么是相交要么是 null 无交点。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) { return null; } ListNode nodeA headA; ListNode nodeB headB; while (nodeA ! nodeB) { nodeA (nodeA null) ? headB : nodeA.next; nodeB (nodeB null) ? headA : nodeB.next; } return nodeA; } }206 反转链表核心逻辑通过 迭代式指针反转法 从链表头节点起始遍历 —— 利用「链表节点仅能单向指向后继节点」的特性以头节点为起始点借助三个指针前驱 / 当前 / 后继每次反转一个节点的指向逐步推进遍历边界无需额外空间且时间复杂度最优高效完成链表反转。关键步骤边界初始化定义前驱指针 prev null、当前指针 curr head迭代反转遍历循环判断curr !null临时存储后继定义temp curr.next保存当前节点的后继节点避免反转后丢失链表后续节点反转节点指向curr.next prev将当前节点的指针从指向后继改为指向前驱完成单次反转推进遍历边界prev curr前驱指针后移指向当前已完成反转的节点curr temp当前指针后移指向待处理的后继节点终止返回当循环因 curr null终止时prev 已指向原链表的最后一个节点返回 prev。public ListNode reverseList(ListNode head) { if (head null) { return null; } ListNode prev null; ListNode curr head; while (curr ! null) { ListNode tempcurr.next; curr.nextprev; prevcurr; currtemp; } return prev; }234 回文链表核心逻辑利用回文的中心对称特性先将链表节点存入数组实现随机访问再通过双指针从数组首尾向中间收缩验证判断是否为回文。关键步骤边界初始化空链表直接返回 false定义数组和遍历指针指向链表头。链表转数组遍历链表将所有节点存入数组。双指针验证左指针从数组头、右指针从数组尾开始对比对应位置值指针向中间收缩直至相遇。终止返回验证完成则返回 true。public boolean isPalindrome(ListNode head) { ListListNode list new ArrayList(); if (head null) { return false; } ListNode currhead; while (curr!null){ list.add(curr); currcurr.next; } int left0; int rightlist.size()-1; while (leftright){ if(list.get(left).val!list.get(right).val){ return false; } right--; left; } return true; }141 环形链表核心逻辑通过 快慢指针追击法 遍历链表 —— 利用「环形链表中快指针终将追上慢指针无环链表中快指针会先到末尾」的特性以快慢双指针从链表头出发快指针步速 2、慢指针步速 1逐步遍历验证无需额外空间且时间复杂度最优高效判断链表是否有环。关键步骤边界初始化定义快指针 fast head、慢指针 slow head均从链表头起始快慢指针遍历循环判断 fast ! null 且 fast.next ! null快指针未到链表末尾快指针步进fast fast.next.next步速 2快速遍历慢指针步进slow slow.next步速 1慢速遍历追击验证若 fast slow快慢指针相遇说明链表有环直接返回 true终止返回当循环因快指针越界终止时说明链表无环返回 false。public boolean hasCycle(ListNode head) { if (head null) { return false; } ListNode fasthead; ListNode slowhead; while (fast!null fast.next!null){ fastfast.next.next; slowslow.next; if(fastslow){ return true; } } return false; }142 环形链表II核心逻辑利用快慢指针相遇后将慢指针重置到链表头两指针同速遍历终将在环入口相遇的数学特性分两步操作先找快慢指针相遇点再通过同速遍历推导环入口无需额外空间且时间复杂度最优。关键步骤边界初始化定义快指针 fast head、慢指针 slow head均从链表头起始找快慢指针相遇点循环判断 fast ! null 且 fast.next ! null快指针未到链表末尾慢指针步进slow slow.next步速 1快指针步进fast fast.next.next步速 2相遇验证若 slow fast快慢指针相遇跳出循环进入阶段 2推导环的入口节点重置慢指针slow head放回链表起始位置同速遍历验证循环判断 slow ! fast两指针未相遇快慢指针均以步速 1 遍历终止返回当 slow fast 时该节点即为环的入口节点返回 slow。public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } // 阶段1找到相遇点 ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { break; } } // 阶段2找环的入口 // 关键操作把慢指针放回起点快慢指针都改为一次走1步 slow head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; }21 合并有序链表核心逻辑通过 虚拟头节点 双指针归并法 合并链表 —— 利用「两个链表本身有序」的特性以虚拟头节点简化边界处理双指针分别遍历两个链表每次选取较小值节点接入结果链表逐步归并无需额外空间且时间复杂度最优高效完成有序链表合并。关键步骤边界初始化定义虚拟头节点 dummy定义归并指针 current dummy指向结果链表的当前末尾双指针归并遍历循环判断 list1 ! null 且 list2 ! null两个链表均未遍历完取值对比若 list1.val list2.val将 list1 接入结果链表current.next list1list1 指针后移反之将 list2 接入结果链表current.next list2list2 指针后移推进结果链表current current.next处理剩余节点循环结束后将未遍历完的链表剩余部分直接接入结果链表current.next list1 或 list2终止返回返回虚拟头节点的后继节点dummy.next即合并后链表的真实头节点。public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy new ListNode(-1); ListNode current dummy; while (list1 ! null list2 ! null) { if (list1.val list2.val) { current.next list1; list1 list1.next; } else { current.next list2; list2 list2.next; } current current.next; } current.next (list1 ! null) ? list1 : list2; return dummy.next; }2 两数相加核心逻辑通过 虚拟头节点 逐位累加进位法 模拟手工加法 —— 利用「链表逆序存储数字头为个位」的特性以虚拟头节点简化结果链表边界处理逐位累加两个链表节点值并带上一轮进位计算当前位值和新进位逐步构建结果链表无需额外空间且时间复杂度最优高效完成链表版两数相加。关键步骤边界初始化定义虚拟头节点 dummy结果链表游标指针 curr dummy进位变量 carry 0逐位累加遍历循环判断 l1 ! null 或 l2 ! null 或 carry ! 0任一链表未遍历完 / 仍有进位初始化累加和sum carry先带上一轮进位累加 l1 当前位若 l1 非空sum l1.vall1 指针后移累加 l2 当前位若 l2 非空sum l2.vall2 指针后移计算进位和当前位carry sum / 10取整得进位value sum % 10取余得位值构建结果链表curr.next new ListNode (value)当前位接入结果链表curr 指针后移终止返回循环结束后返回 dummy.next虚拟头节点的后继节点即结果链表真实头节点。public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummynew ListNode(0); ListNode currdummy; int carry0; int sum0; while (l1!null || l2!null || carry!0){ sumcarry; if(l1!null){ suml1.val; l1l1.next; } if(l2!null){ suml2.val; l2l2.next; } carrysum/10; sumsum%10; curr.nextnew ListNode(sum); currcurr.next; } return dummy.next; }19 删除链表的倒数第 N 个结点核心逻辑通过 快慢指针间隔定位法 定位待删节点 —— 利用「快慢指针拉开 n1 步间隔后同速遍历快指针到末尾时慢指针恰好指向待删节点前驱」的特性以虚拟头节点规避边界问题无需计算链表长度且时间复杂度最优高效删除倒数第 N 个节点。关键步骤边界初始化定义虚拟头节点 dummydummy.next head定义慢指针 slow dummy、快指针 fast dummy均从虚拟头节点起始快慢指针拉开间隔循环 n1 次让 fast 指针先走 n1 步确保慢指针最终指向待删节点的前驱每次循环执行 fast fast.next同速遍历定位前驱循环判断 fast ! null快指针未到链表末尾慢指针步进slow slow.next步速 1快指针步进fast fast.next步速 1当 fast 为 null 时slow 恰好指向「倒数第 n1 个节点」待删节点的直接前驱删除节点并返回执行 slow.next slow.next.next返回 dummy.next。public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode slow dummy; ListNode fast dummy; for (int i 0; i n; i) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } slow.next slow.next.next; return dummy.next; }24 两两交换链表中的节点核心逻辑通过 虚拟头节点 迭代交换法 实现节点两两交换 —— 利用「虚拟头节点简化头节点交换的边界处理」的特性以虚拟头节点为起始点每次迭代锁定待交换的两个节点通过调整指针指向完成局部交换逐步推进遍历边界无需额外空间且时间复杂度最优高效完成两两交换。关键步骤边界初始化定义虚拟头节点 dummydummy.next head定义遍历指针 curr dummy迭代交换遍历循环判断 curr.next ! null 且 curr.next.next ! null存在可交换的两个节点锁定待交换节点定义 node1 curr.next第一个节点、node2 curr.next.next第二个节点调整指针完成交换curr.next node2前驱节点指向第二个待交换节点完成交换第一步node1.next node2.next第一个节点指向第二个节点的后继避免链表断裂node2.next node1第二个节点指向第一个节点完成交换第二步准备下一轮交换curr curr.next.next终止返回当循环因无足够可交换节点终止时返回 dummy.next。public ListNode swapPairs(ListNode head) { ListNode dummynew ListNode(0,head); ListNode currdummy; while (curr.next!null curr.next.next!null){ ListNode node1curr.next; ListNode node2curr.next.next; curr.nextnode2; node1.nextnode2.next; node2.nextnode1; currcurr.next.next; } return dummy.next; }138 随机链表的复制核心逻辑通过 三步复制法 实现深拷贝 —— 利用链表的链式遍历特性先在原链表每节点后新增复制节点再依次设定复制节点的 random 指针最后拆分原链表与复制链表通过三次线性遍历完成无哈希表依赖的深拷贝确保所有指针指向全新节点。关键步骤节点插入复制遍历原链表在每个原节点后新建一个复制节点将原节点值写入新节点使原链表变为原节点 - 复制节点 - 原节点.next - ...的交错结构。指定 random 指针再次遍历链表定位到复制节点将其 random 指针指向对应原节点的 random 指针所指向节点的下一个节点即复制节点完成 random 指针的深指向。拆分链表分离第三次遍历链表拆出交错链表中的复制节点重新构建成新的复制链表同时恢复原链表的 next 指针返回复制链表头节点。public Node copyRandomList(Node head) { if (head null) { return null; } Node cur head; while (cur ! null) { Node copyNode new Node(cur.val); copyNode.next cur.next; cur.next copyNode; cur copyNode.next; } cur head; while (cur ! null) { Node copyNode cur.next; if (cur.random ! null) { copyNode.random cur.random.next; } cur copyNode.next; } cur head; Node copyHead head.next; while (cur ! null) { Node copyNode cur.next; cur.next copyNode.next; if (copyNode.next ! null) { copyNode.next copyNode.next.next; } cur cur.next; } return copyHead; }148 排序链表核心逻辑通过 归并排序分治归并法 实现链表排序 —— 利用「归并排序分而治之 链表可通过指针拆分 / 合并」的特性先以快慢指针找链表中点拆分链表递归排序左右子链表再合并两个有序子链表无需额外空间递归栈除外且时间复杂度最优高效完成链表排序。关键步骤边界初始化处理空链表 / 单节点链表边界情况head 为 null 或 head.next 为 null 直接返回 找中点拆分链表定义快慢指针找链表中点的前驱节点快指针为 head.next慢指针步进slow slow.next步速 1快指针步进fast fast.next.next步速 2拆分操作midPrev.next null 切断链表拆分出左子链表head和右子链表midPrev.next递归排序子链表分别递归排序左子链表sortList (head)和右子链表sortList (right)合并有序链表初始化虚拟头节点 dummy逐位比较两个有序子链表节点值将较小值节点接入结果链表拼接剩余节点后返回 dummy.next终止返回递归逐层合并完成后返回最终的有序链表头节点。public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } ListNode midPrev findMidPrev(head); ListNode right midPrev.next; midPrev.next null; ListNode leftSorted sortList(head); ListNode rightSorted sortList(right); return mergeTwoSortedLists(leftSorted, rightSorted); } private ListNode findMidPrev(ListNode head) { ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode curr dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { curr.next l1; l1 l1.next; } else { curr.next l2; l2 l2.next; } curr curr.next; } curr.next (l1 ! null) ? l1 : l2; return dummy.next; }146 LRU 缓存核心逻辑通过 哈希表 双向链表 实现 LRU 缓存 —— 利用哈希表实现 O (1) 时间的键值查找利用双向链表维护最近使用顺序头部为最近使用尾部为最久未使用每次访问或插入时将节点移到头部容量不足时删除尾部节点保证get和put操作均为 O (1) 平均时间复杂度。关键步骤边界初始化定义双向链表节点Node包含key、value、prev、next初始哈希表cache存储键节点映射、虚拟头节点head、虚拟尾节点tail、容量capacity连接head和tail构建空链表。get 操作获取值若 key 不存在于cache返回 -1若存在取出对应节点node将node从链表中移除将node插入到链表头部标记为最近使用返回node.value。put 操作插入 / 更新值若 key 已存在取出节点node更新其value将node从链表中移除再插入到链表头部若 key 不存在新建节点newNode将其插入链表头部将key → newNode映射存入哈希表若缓存容量超过capacity删除链表尾部节点最久未使用从哈希表中移除该节点的 key 映射。辅助操作链表维护removeNode(Node node)从链表中移除指定节点addToHead(Node node)将节点插入到链表头部head之后removeTail()删除链表尾部节点tail之前并返回该节点。class LRUCache { class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key key; this.value value; } } private MapInteger, Node cache; private int capacity; private Node head; private Node tail; private int size; public LRUCache(int capacity) { this.capacity capacity; this.size 0; this.cache new HashMap(); //虚拟头尾节点 this.head new Node(0, 0); this.tail new Node(0, 0); head.next tail; tail.prev head; } public int get(int key) { Node node cache.get(key); if (node null) { return -1; } // 移动到头部 removeNode(node); addToHead(node); return node.value; } public void put(int key, int value) { Node node cache.get(key); if (node null) { // 新建节点 Node newNode new Node(key, value); cache.put(key, newNode); addToHead(newNode); size; // 容量不足删除尾部 if (size capacity) { Node tailNode removeTail(); cache.remove(tailNode.key); size--; } } else { // 更新值并移动到头部 node.value value; removeNode(node); addToHead(node); } } // 移除指定节点 private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } // 添加到头部 private void addToHead(Node node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 删除尾部节点 private Node removeTail() { Node tailNode tail.prev; removeNode(tailNode); return tailNode; } }恭喜你学习完成✿