链表
更新: 9/11/2025 字数: 0 字 时长: 0 分钟
相交链表
java
/**
* <p>此方法解决“相交链表”问题，旨在找出两个单链表相交的起始节点。</p>
* <p>核心思想是使用“双指针法”，通过巧妙地将指针重定向到另一个链表的头部，
* 使得两个指针最终走过相同的总距离，从而在相交点相遇。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化指针：</strong>
* <ul>
* <li>初始化两个指针 {@code pA = headA} 和 {@code pB = headB}。</li>
* <li>处理特殊情况：如果任何一个链表为空，它们不可能相交（除非两者都为空且被认为是相交在 null），
* 但问题要求返回相交节点，所以如果有一个为 null，直接返回 null 即可。</li>
* </ul>
* </li>
* <li><strong>循环查找相交点：</strong>
* <ul>
* <li>进入一个 {@code while (pA != pB)} 循环。
* <ul>
* <li>如果 {@code pA} 不为 {@code null}，则 {@code pA = pA.next}。</li>
* <li>否则 (即 {@code pA} 到达链表 A 的末尾)，将 {@code pA} 重新指向链表 B 的头部 ({@code pA = headB})。</li>
* <li>如果 {@code pB} 不为 {@code null}，则 {@code pB = pB.next}。</li>
* <li>否则 (即 {@code pB} 到达链表 B 的末尾)，将 {@code pB} 重新指向链表 A 的头部 ({@code pB = headA})。</li>
* </ul>
* </li>
* <li>循环会一直进行，直到 {@code pA == pB}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当循环结束时，{@code pA} (或 {@code pB}) 就是相交节点。
* <ul>
* <li>如果链表相交，{@code pA} 和 {@code pB} 会在相交点相遇。</li>
* <li>如果链表不相交，它们最终都会同时变为 {@code null}，此时 {@code pA == pB} ({@code null == null})。</li>
* </ul>
* 因此，直接返回 {@code pA} 即可。</li>
* </ul>
* </li>
* </ol>
*
* <h3>原理详解：</h3>
* <p>假设链表 A 独有部分长度为 {@code a}，链表 B 独有部分长度为 {@code b}，相交部分长度为 {@code c}。</p>
* <p>指针 {@code pA} 走的路径：{@code a -> c -> b -> c} (总长度 {@code a + c + b + c})</p>
* <p>指针 {@code pB} 走的路径：{@code b -> c -> a -> c} (总长度 {@code b + c + a + c})</p>
* <p>两个指针最终走过的总距离是相同的。当它们都走了 {@code a + b + c} 距离时：</p>
* <ul>
* <li>如果链表相交，它们会在相交点（共同部分 {@code c} 的起点）相遇。</li>
* <li>如果链表不相交 (即 {@code c = 0})，它们最终会同时到达两个链表的末尾，即都变为 {@code null}，从而相遇。</li>
* </ul>
* <p>因此，无论是否相交，{@code pA} 和 {@code pB} 最终会在同一个节点 (相交节点或 {@code null}) 相遇。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M + N)}。
* <ul>
* <li>其中 M 和 N 分别是两个链表的长度。每个节点最多被访问两次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 如果任何一个链表为空，则不可能相交，直接返回 null
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA;
ListNode pB = headB;
// 循环直到 pA == pB
// 两种情况会使 pA == pB 终止循环：
// 1. 它们在相交节点相遇
// 2. 它们都变为 null (表示不相交)
while (pA != pB) {
// 如果 pA 到达链表 A 的末尾，则将其指向链表 B 的头部
// 否则，pA 继续向前移动
pA = (pA == null) ? headB : pA.next;
// 如果 pB 到达链表 B 的末尾，则将其指向链表 A 的头部
// 否则，pB 继续向前移动
pB = (pB == null) ? headA : pB.next;
}
// 此时 pA (或 pB) 就是相交节点，如果它们不相交，则 pA 此时为 null
return pA;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}反转链表
java
/**
* <p>此方法通过<strong>迭代法</strong>反转单链表。</p>
* <p>核心思想是使用三个指针：
* <ul>
* <li>{@code prev}: 指向当前节点的前一个节点，初始化为 {@code null}。</li>
* <li>{@code curr}: 指向当前正在处理的节点，初始化为链表的头节点 {@code head}。</li>
* <li>{@code nextTemp}: 临时存储 {@code curr} 的下一个节点，以防在修改 {@code curr.next} 后丢失后续链表的引用。</li>
* </ul>
* </p>
* <p>在每次迭代中，我们做三件事：
* 1. 保存 {@code curr} 的下一个节点。
* 2. 将 {@code curr.next} 指向 {@code prev}，完成当前节点的反转。
* 3. 更新 {@code prev} 和 {@code curr}，为下一次迭代做准备。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li>初始化 {@code prev = null} 和 {@code curr = head}。</li>
* <li>进入 {@code while (curr != null)} 循环：
* <ol type="a">
* <li>{@code ListNode nextTemp = curr.next;} (保存 {@code curr} 的下一个节点)</li>
* <li>{@code curr.next = prev;} (将 {@code curr} 的 {@code next} 指针指向 {@code prev}，完成反转)</li>
* <li>{@code prev = curr;} (更新 {@code prev} 为当前节点，为下一次迭代做准备)</li>
* <li>{@code curr = nextTemp;} (更新 {@code curr} 为下一个节点，继续遍历)</li>
* </ol>
* </li>
* <li>循环结束后，{@code curr} 会变为 {@code null}，而 {@code prev} 会指向原链表的最后一个节点，即反转后链表的头节点。</li>
* <li>返回 {@code prev}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 N 是链表的节点数量。我们遍历链表一次，每个节点的操作都是常数时间。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了几个常数个额外指针变量。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 1. 保存下一个节点
curr.next = prev; // 2. 当前节点指向前一个节点 (反转操作)
prev = curr; // 3. prev 移动到当前节点
curr = nextTemp; // 4. curr 移动到下一个节点
}
return prev; // prev 最终会是反转后链表的头节点
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法通过<strong>递归法</strong>反转单链表。</p>
* <p>核心思想是：将问题分解为“反转子链表”和“将当前节点连接到反转后的子链表末尾”。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>基本情况 (Base Case)：</strong>
* <ul>
* <li>如果链表为空 ({@code head == null}) 或者链表只有一个节点 ({@code head.next == null})，
* 说明已经到达链表末尾或者链表无需反转，直接返回 {@code head}。</li>
* </ul>
* </li>
* <li><strong>递归调用：</strong>
* <ul>
* <li>递归地调用 {@code reverseListRecursive(head.next)} 来反转 {@code head} 之后的子链表。
* 将返回的结果存储在 {@code newHead} 中。此时 {@code newHead} 是整个反转后链表的头节点。</li>
* </ul>
* </li>
* <li><strong>连接当前节点：</strong>
* <ul>
* <li>在 {@code reverseListRecursive(head.next)} 调用返回后：
* <ul>
* <li>{@code head.next} 指向的是原链表的第二个节点。在递归调用中，这个第二个节点已经成为了反转后子链表的尾节点。</li>
* <li>所以，我们让 {@code head.next.next = head;}，即将原链表的第二个节点的 {@code next} 指针指向 {@code head}。
* 这样，{@code head} 就被连接到了反转后的子链表的末尾。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>断开旧连接：</strong>
* <ul>
* <li>将 {@code head.next = null;}。这是因为 {@code head} 节点现在是反转后链表的尾节点，它的 {@code next} 应该指向 {@code null}。</li>
* </ul>
* </li>
* <li><strong>返回：</strong>
* <ul>
* <li>返回 {@code newHead}。这个 {@code newHead} 是从最深层递归（原链表最后一个节点）返回的，它始终是整个反转后链表的头节点。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 N 是链表的节点数量。每个节点被访问一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>这是由于递归调用栈的深度，最坏情况下（链表没有环）会达到 N。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode reverseList(ListNode head) {
// 基本情况：链表为空或只有一个节点
if (head == null || head.next == null) {
return head;
}
// 递归反转 head 之后的子链表
ListNode newHead = reverseList(head.next);
// 将当前节点 head 连接到反转后的子链表的末尾
// 此时 head.next 是原链表的第二个节点，也是反转后子链表的尾节点
head.next.next = head;
// 当前节点 head 变为反转后链表的尾节点，其 next 指向 null
head.next = null;
// 返回反转后链表的头节点
return newHead;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}回文链表
java
/**
* <p>此方法使用 {@code ArrayList} 来判断链表是否为回文链表。</p>
* <p>核心思想是将链表的所有节点值复制到一个列表中，然后使用双指针法判断列表是否为回文。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理空链表：</strong>如果 {@code head} 为 {@code null}，空链表是回文，返回 {@code true}。</li>
* <li><strong>遍历链表并存储元素：</strong>
* <ul>
* <li>创建一个 {@code ArrayList<Integer> list}。</li>
* <li>使用一个 {@code current} 指针从 {@code head} 开始遍历链表。</li>
* <li>将每个节点的 {@code val} 添加到 {@code list} 中。</li>
* </ul>
* </li>
* <li><strong>双指针判断回文：</strong>
* <ul>
* <li>初始化两个指针 {@code left = 0} 和 {@code right = list.size() - 1}。</li>
* <li>进入 {@code while (left < right)} 循环：
* <ul>
* <li>如果 {@code list.get(left)} 不等于 {@code list.get(right)}，则不是回文，返回 {@code false}。</li>
* <li>否则，{@code left++}，{@code right--}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>如果循环完成，说明是回文，返回 {@code true}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>遍历链表并添加到列表需要 O(N) 时间。</li>
* <li>双指针判断列表回文需要 O(N) 时间。</li>
* <li>总计 O(N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>{@code ArrayList} 需要存储链表中所有 N 个节点的值。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true; // 空链表是回文
}
List<Integer> list = new ArrayList<>();
ListNode current = head;
while (current != null) {
list.add(current.val);
current = current.next;
}
int left = 0;
int right = list.size() - 1;
while (left < right) {
if (!list.get(left).equals(list.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法使用 {@code StringBuilder} 来判断链表是否为回文链表。</p>
* <p>核心思想是将链表的所有节点值连接成一个字符串，然后判断该字符串是否为回文。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理空链表：</strong>如果 {@code head} 为 {@code null}，空链表是回文，返回 {@code true}。</li>
* <li><strong>遍历链表并构建字符串：</strong>
* <ul>
* <li>创建一个 {@code StringBuilder sb}。</li>
* <li>使用一个 {@code current} 指针从 {@code head} 开始遍历链表。</li>
* <li>将每个节点的 {@code val} 追加到 {@code sb} 中。</li>
* </ul>
* </li>
* <li><strong>判断回文：</strong>
* <ul>
* <li>将 {@code sb} 转换为 {@code String originalString = sb.toString()}。</li>
* <li>创建 {@code StringBuilder} 的反转版本并转换为字符串：
* {@code String reversedString = sb.reverse().toString()}。</li>
* <li>比较 {@code originalString} 和 {@code reversedString} 是否相等。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>根据比较结果返回 {@code true} 或 {@code false}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>遍历链表并构建字符串需要 O(N) 时间。</li>
* <li>字符串反转和比较需要 O(N) 时间。</li>
* <li>总计 O(N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>{@code StringBuilder} 需要存储链表中所有 N 个节点值转换成的字符串。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true; // 空链表是回文
}
StringBuilder sb = new StringBuilder();
ListNode current = head;
while (current != null) {
sb.append(current.val);
current = current.next;
}
String originalString = sb.toString();
String reversedString = sb.reverse().toString(); // sb 已经被修改，直接反转即可
return originalString.equals(reversedString);
}
// ListNode 类的定义 (与上面相同)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法使用<strong>快慢指针 + 反转链表</strong>的策略，以 O(1) 空间复杂度判断链表是否为回文链表。</p>
* <p>核心思想是：
* 1. 使用快慢指针找到链表的中间节点。
* 2. 反转链表的后半部分。
* 3. 比较链表的前半部分和反转后的后半部分。
* 4. (可选) 恢复链表原始结构。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理特殊情况：</strong>如果 {@code head} 为 {@code null} 或只有一个节点，返回 {@code true}。</li>
* <li><strong>寻找中点：</strong>
* <ul>
* <li>使用 {@code slow} 和 {@code fast} 指针，都从 {@code head} 开始。</li>
* <li>{@code slow} 每次走一步，{@code fast} 每次走两步。</li>
* <li>当 {@code fast} 到达链表末尾时 ({@code fast == null} 或 {@code fast.next == null})，{@code slow} 恰好在中点。
* 具体来说，{@code slow} 停在前半部分的最后一个节点，或者中间偏左的那个节点。</li>
* </ul>
* </li>
* <li><strong>反转后半部分链表：</strong>
* <ul>
* <li>调用辅助函数 {@code reverseList(slow.next)} 来反转从 {@code slow.next} 开始的链表后半部分。</li>
* <li>将返回的头节点保存为 {@code secondHalfHead}。</li>
* <li><strong>注意：</strong> 此时 {@code slow} 节点是前半部分的末尾。我们将其 {@code next} 设置为 {@code null} 以暂时断开两部分，方便比较。
* {@code slow.next = null;} (这个断开操作很重要，否则前半部分会继续指向反转前的后半部分，导致混乱)</li>
* </ul>
* </li>
* <li><strong>比较前半部分和反转后的后半部分：</strong>
* <ul>
* <li>初始化 {@code p1 = head} 和 {@code p2 = secondHalfHead}。</li>
* <li>同时遍历 {@code p1} 和 {@code p2}，比较它们的值。</li>
* <li>如果发现任何一对不相等，立即返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>（可选）恢复链表：</strong>
* <ul>
* <li>如果题目要求不修改原链表，需要在比较完成后将 {@code secondHalfHead} 再次反转，
* 然后将 {@code slow.next} 重新指向恢复后的后半部分的头节点。</li>
* <li>{@code ListNode originalSecondHalfHead = reverseList(secondHalfHead);}</li>
* <li>{@code slow.next = originalSecondHalfHead;}</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>如果所有比较都通过，返回 {@code true}。</li>
* </ol>
*
* <h3>辅助函数 {@code reverseList(ListNode head)}：</h3>
* <p>这是一个标准的迭代反转链表函数，在上面的 206 题中已经实现过。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>寻找中点、反转后半部分、比较、恢复链表（如果需要）都各自需要 O(N/2) 的时间。</li>
* <li>总计 O(N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true; // 空链表或单节点链表是回文
}
// 1. 使用快慢指针找到链表的中间节点
ListNode slow = head;
ListNode fast = head;
// fast 走到末尾时，slow 走到中点。
// 如果链表是奇数长，fast 停在最后一个节点，slow 停在正中间。
// 如果链表是偶数长，fast 停在 null，slow 停在前半部分的最后一个节点。
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 此时 slow 指向前半部分的末尾节点 (或中间节点)
// 2. 反转后半部分链表
// 从 slow.next 开始反转，得到反转后的后半部分的头节点
ListNode secondHalfHead = reverseList(slow.next);
// 3. 将前半部分和反转后的后半部分进行比较
ListNode p1 = head; // 前半部分头
ListNode p2 = secondHalfHead; // 反转后的后半部分头
boolean isPalindrome = true; // 默认是回文
while (p1 != null && p2 != null) { // 遍历直到其中一个指针到达末尾
if (p1.val != p2.val) {
isPalindrome = false;
break; // 不匹配，不是回文
}
p1 = p1.next;
p2 = p2.next;
}
// 4. (可选) 恢复链表原始结构 - 如果不允许修改原链表
// 先将反转的后半部分再次反转
// 再将前半部分和恢复后的后半部分连接起来
slow.next = reverseList(secondHalfHead);
return isPalindrome;
}
/**
* 辅助函数：反转链表 (迭代法)
* 在 206 题中已实现
*/
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// ListNode 类的定义 (与上面相同)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}环形链表
java
/**
* <p>此方法解决“环形链表”问题，旨在判断链表中是否存在环。</p>
* <p>核心思想是使用<strong>快慢指针法</strong>（Floyd's Cycle-Finding Algorithm）。
* 一个慢指针 {@code slow} 每次走一步，一个快指针 {@code fast} 每次走两步。
* 如果链表有环，{@code fast} 指针最终会追上 {@code slow} 指针。
* 如果链表无环，{@code fast} 指针会先到达链表的末尾（{@code null}）。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理特殊情况：</strong>
* <ul>
* <li>如果链表为空 ({@code head == null}) 或者链表只有一个节点 ({@code head.next == null})，
* 那么肯定不存在环，直接返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>初始化指针：</strong>
* <ul>
* <li>初始化慢指针 {@code slow = head}。</li>
* <li>初始化快指针 {@code fast = head.next}。
* （这里让 {@code fast} 比 {@code slow} 先走一步，是为了确保它们不会在环的入口处就因为初始位置相同而立即判定为相遇，
* 避免误判，因为在 {@code while} 循环中会先进行判断 {@code slow == fast}。）</li>
* </ul>
* </li>
* <li><strong>循环判断：</strong>
* <ul>
* <li>进入一个 {@code while (fast != null && fast.next != null)} 循环。
* 这个条件确保 {@code fast} 在每次移动两步前都有足够的节点。</li>
* <li>在循环内部：
* <ul>
* <li>首先，检查 {@code slow == fast}。如果相等，则说明快慢指针相遇，链表存在环，返回 {@code true}。</li>
* <li>然后，移动指针：
* <ul>
* <li>{@code slow = slow.next} (慢指针向前移动一步)</li>
* <li>{@code fast = fast.next.next} (快指针向前移动两步)</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果循环结束（即 {@code fast} 或 {@code fast.next} 变为 {@code null}），
* 说明快指针已到达链表末尾，链表中不存在环，返回 {@code false}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>在没有环的情况下，快指针最多遍历 N 个节点，慢指针最多遍历 N/2 个节点。</li>
* <li>在有环的情况下，当快慢指针都进入环后，它们之间的距离会不断缩小，最终会在环内相遇。
* 快指针最多走两圈就能追上慢指针。总的遍历次数仍是链表长度的常数倍。</li>
* <li>因此，总时间复杂度为 O(N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了两个额外指针变量。</li>
* </ul>
* </li>
* </ul>
*/
public boolean hasCycle(ListNode head) {
// 特殊情况：空链表或只有一个节点的链表不可能有环
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next; // fast 比 slow 先走一步
// 循环条件：fast 和 fast.next 都不能为 null
// 确保 fast 每次都能移动两步
while (fast != null && fast.next != null) {
// 如果快慢指针相遇，则存在环
if (slow == fast) {
return true;
}
// 慢指针走一步
slow = slow.next;
// 快指针走两步
fast = fast.next.next;
}
// 循环结束，fast 到达链表末尾，没有环
return false;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}环形链表 II
java
/**
* <p>此方法解决“环形链表 II”问题，旨在找出链表开始入环的第一个节点。</p>
* <p>核心思想是<strong>快慢指针法</strong>（Floyd's Cycle-Finding Algorithm）的扩展：
* 1. 首先，使用快慢指针检测链表中是否存在环，并找到它们的相遇点。
* 2. 如果存在环，通过数学推导，我们可以确定从链表头和相遇点同时以相同速度移动，它们会在环的入口点相遇。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>处理特殊情况：</strong>
* <ul>
* <li>如果链表为空 ({@code head == null}) 或者链表只有一个节点 ({@code head.next == null})，
* 则不可能有环，直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>第一阶段：检测环并找到相遇点。</strong>
* <ul>
* <li>初始化 {@code slow = head} 和 {@code fast = head}。</li>
* <li>进入 {@code while (fast != null && fast.next != null)} 循环：
* <ul>
* <li>{@code slow = slow.next} (慢指针走一步)</li>
* <li>{@code fast = fast.next.next} (快指针走两步)</li>
* <li>如果 {@code slow == fast}，说明快慢指针相遇，链表存在环。此时跳出循环，进入第二阶段。</li>
* </ul>
* </li>
* <li>如果循环结束后（即 {@code fast} 或 {@code fast.next} 变为 {@code null}），
* 说明快指针已到达链表末尾，链表中不存在环，返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>第二阶段：找到环的入口点。</strong>
* <ul>
* <li>将 {@code slow} 指针重新指向链表的头部 ({@code slow = head})。</li>
* <li>现在，{@code slow} 从 {@code head} 开始，{@code fast} 从相遇点开始。
* 让它们都以每次一步的速度向前移动。</li>
* <li>进入 {@code while (slow != fast)} 循环：
* <ul>
* <li>{@code slow = slow.next}</li>
* <li>{@code fast = fast.next}</li>
* </ul>
* </li>
* <li>当循环结束时，{@code slow == fast}，它们相遇的节点就是环的入口节点。返回 {@code slow} (或 {@code fast})。</li>
* </ul>
* </li>
* </ol>
*
* <h3>数学推导 (为何第二阶段有效)：</h3>
* <p>设：</p>
* <ul>
* <li>{@code a}：链表头到环入口的距离。</li>
* <li>{@code b}：环入口到快慢指针第一次相遇点的距离。</li>
* <li>{@code R}：环的长度。</li>
* </ul>
* <p>当快慢指针相遇时：</p>
* <ul>
* <li>慢指针 {@code slow} 走过的距离：{@code L_slow = a + b}。</li>
* <li>快指针 {@code fast} 走过的距离：{@code L_fast = a + b + kR} (其中 {@code k} 是 {@code fast} 在环中比 {@code slow} 多走的圈数)。</li>
* <li>由于 {@code fast} 速度是 {@code slow} 的两倍：{@code L_fast = 2 * L_slow}。</li>
* </ul>
* <p>代入并化简：</p>
* <p>{@code a + b + kR = 2 * (a + b)}</p>
* <p>{@code a + b + kR = 2a + 2b}</p>
* <p>{@code kR = a + b}</p>
* <p>进一步变形：</p>
* <p>{@code a = kR - b}</p>
* <p>{@code a = (k - 1)R + (R - b)}</p>
* <p>这个公式意味着：从链表头 {@code head} 走 {@code a} 步到达环入口。从相遇点继续走 {@code R - b} 步 (即绕环一周回到入口) 也到达环入口。
* {@code a} 步的距离 等于 {@code (k-1)} 圈的距离加上 {@code R-b} 步的距离。
* 所以，如果我们将一个指针从 {@code head} 开始，另一个指针从相遇点开始，并且它们都以一步的速度前进，它们必然会在环的入口处相遇。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>第一阶段寻找相遇点最多遍历 N 个节点。</li>
* <li>第二阶段寻找环入口最多遍历 N 个节点。</li>
* <li>总时间复杂度为 O(N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了两个额外指针变量。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode detectCycle(ListNode head) {
// 特殊情况：空链表或单节点链表不可能有环
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
// 第一阶段：检测环并找到相遇点
// fast 每次走两步，slow 每次走一步
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 如果相遇，则存在环
if (slow == fast) {
// 进入第二阶段
break;
}
}
// 如果循环结束时 fast == null 或 fast.next == null，说明没有环
if (fast == null || fast.next == null) {
return null;
}
// 第二阶段：找到环的入口点
// 将 slow 重新指向 head
slow = head;
// fast 保持在相遇点
// 两个指针都以一步的速度前进，它们会在环的入口处相遇
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 相遇点就是环的入口
return slow;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}合并两个有序链表
java
/**
* <p>此方法通过<strong>迭代法</strong>合并两个有序链表。</p>
* <p>核心思想是使用一个虚拟头节点（dummy node）来简化合并操作，并利用一个 {@code current} 指针逐一比较两个输入链表的节点，
* 将值较小的节点添加到新链表的末尾。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>创建一个 {@code ListNode dummyHead = new ListNode(-1);}。这个节点不包含实际数据，只是作为新链表的起点辅助。</li>
* <li>创建一个 {@code ListNode current = dummyHead;}。{@code current} 指针将始终指向新链表的当前末尾，用于连接下一个节点。</li>
* </ul>
* </li>
* <li><strong>遍历并合并：</strong>
* <ul>
* <li>进入 {@code while (list1 != null && list2 != null)} 循环：
* <ol type="a">
* <li>比较 {@code list1.val} 和 {@code list2.val}。</li>
* <li>如果 {@code list1.val <= list2.val}：
* <ul>
* <li>将 {@code list1} 的当前节点连接到 {@code current} 的后面：{@code current.next = list1;}。</li>
* <li> {@code list1} 指针向前移动一步：{@code list1 = list1.next;}。</li>
* </ul>
* </li>
* <li>否则 (即 {@code list2.val < list1.val})：
* <ul>
* <li>将 {@code list2} 的当前节点连接到 {@code current} 的后面：{@code current.next = list2;}。</li>
* <li>{@code list2} 指针向前移动一步：{@code list2 = list2.next;}。</li>
* </ul>
* </li>
* <li>{@code current} 指针向前移动到刚刚添加的节点，以便为下一次连接做准备：{@code current = current.next;}。</li>
* </ol>
* </li>
* </ul>
* </li>
* <li><strong>处理剩余节点：</strong>
* <ul>
* <li>当 {@code while} 循环结束时，说明 {@code list1} 或 {@code list2} 中至少有一个已经遍历完。</li>
* <li>将非空的那个链表的剩余部分（如果有）直接连接到新链表的末尾：
* {@code current.next = (list1 != null) ? list1 : list2;}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>新的合并链表的头节点是 {@code dummyHead.next}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M + N)}。
* <ul>
* <li>其中 M 和 N 分别是 {@code list1} 和 {@code list2} 的长度。</li>
* <li>每次迭代都会将一个节点从 {@code list1} 或 {@code list2} 添加到新链表，或者移动一个指针。</li>
* <li>总共需要处理 M + N 个节点。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针变量 (dummyHead, current, list1, list2)。我们是在复用现有节点，而不是创建新节点。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建一个虚拟头节点，它的 next 将指向合并后的链表的真正头节点
ListNode dummyHead = new ListNode(-1);
// current 指针用于构建新链表，它总是指向新链表的末尾
ListNode current = dummyHead;
// 当两个链表都不为空时，逐个比较并连接节点
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1; // 将 list1 的当前节点连接到新链表
list1 = list1.next; // list1 向前移动
} else {
current.next = list2; // 将 list2 的当前节点连接到新链表
list2 = list2.next; // list2 向前移动
}
current = current.next; // current 指针总是指向新链表的末尾
}
// 如果其中一个链表还有剩余节点，直接将其连接到新链表的末尾
current.next = list1 != null ? list1 : list2;
// 更简洁的写法：current.next = (list1 != null) ? list1 : list2;
// 返回虚拟头节点的下一个节点，即合并后链表的真正头节点
return dummyHead.next;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法通过<strong>递归法</strong>合并两个有序链表。</p>
* <p>核心思想是：如果两个链表都非空，就比较它们的头节点，选择较小的一个作为当前合并链表的头节点，
* 然后递归地合并剩余的链表部分。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>基本情况 (Base Cases)：</strong>
* <ul>
* <li>如果 {@code list1} 为 {@code null}，说明它已遍历完，直接返回 {@code list2} (list2 的剩余部分)。</li>
* <li>如果 {@code list2} 为 {@code null}，说明它已遍历完，直接返回 {@code list1} (list1 的剩余部分)。</li>
* </ul>
* </li>
* <li><strong>递归调用：</strong>
* <ul>
* <li>比较 {@code list1.val} 和 {@code list2.val}：
* <ol type="a">
* <li>如果 {@code list1.val <= list2.val}：
* <ul>
* <li>选择 {@code list1} 作为当前合并部分的头节点。</li>
* <li>将 {@code list1.next} 指针指向 {@code list1.next} 和 {@code list2} 递归合并后的结果。</li>
* <li>返回 {@code list1}。</li>
* </ul>
* </li>
* <li>否则 (即 {@code list2.val < list1.val})：
* <ul>
* <li>选择 {@code list2} 作为当前合并部分的头节点。</li>
* <li>将 {@code list2.next} 指针指向 {@code list1} 和 {@code list2.next} 递归合并后的结果。</li>
* <li>返回 {@code list2}。</li>
* </ul>
* </li>
* </ol>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(M + N)}。
* <ul>
* <li>其中 M 和 N 分别是 {@code list1} 和 {@code list2} 的长度。</li>
* <li>每次递归调用都会处理一个节点，或者使得一个链表指针向前移动。</li>
* <li>总共会进行 M + N 次有效比较和连接操作。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(M + N)}。
* <ul>
* <li>这是由于递归调用栈的深度，最坏情况下（例如一个链表很长，另一个链表很短）会达到 M + N 层。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// Base Cases
// 如果 list1 为空，返回 list2 的剩余部分
if (list1 == null) {
return list2;
}
// 如果 list2 为空，返回 list1 的剩余部分
if (list2 == null) {
return list1;
}
// 递归步骤
// 比较当前两个节点的 L 值
if (list1.val <= list2.val) {
// 如果 list1 的值较小，则 list1 是合并后链表的头节点
// 递归地合并 list1.next 和 list2
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
// 如果 list2 的值较小，则 list2 是合并后链表的头节点
// 递归地合并 list1 和 list2.next
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
// ListNode 类的定义 (与上面相同)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}两数相加
java
/**
* <p>此方法解决“两数相加”问题，通过<strong>迭代法</strong>模拟小学列竖式加法。</p>
* <p>核心思想是：同时遍历两个链表，逐位数字相加，并处理进位（carry）。
* 由于数字是逆序存储的，这恰好是小学生从个位开始加的方式。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个<strong>虚拟头节点</strong> {@code dummyHead = new ListNode(0);}。
* 它的作用是简化代码，避免对结果链表的第一个节点进行特殊判断。最终结果将从 {@code dummyHead.next} 开始。</li>
* <li>创建一个<strong>当前指针</strong> {@code current = dummyHead;}。
* {@code current} 将始终指向正在构建的结果链表的最后一个节点。</li>
* <li>初始化<strong>进位</strong> {@code carry = 0;}。</li>
* </ul>
* </li>
* <li><strong>遍历并相加：</strong>
* <ul>
* <li>进入 {@code while (l1 != null || l2 != null)} 循环。
* 只要其中一个链表还有节点（或者两者都有），就继续进行加法。
* 这个条件也隐式处理了两个链表长度不一致的情况。</li>
* <li>在循环内部：
* <ol type="a">
* <li><strong>获取当前位的值：</strong>
* <ul>
* <li>{@code int val1 = (l1 != null) ? l1.val : 0;} (如果 {@code l1} 为空，则当前位值为 0)。</li>
* <li>{@code int val2 = (l2 != null) ? l2.val : 0;} (如果 {@code l2} 为空，则当前位值为 0)。</li>
* </ul>
* </li>
* <li><strong>计算当前位的和：</strong>
* <ul>
* <li>{@code int sum = val1 + val2 + carry;} (加上两个数字的当前位和上一轮的进位)。</li>
* </ul>
* </li>
* <li><strong>更新进位：</strong>
* <ul>
* <li>{@code carry = sum / 10;} (整数除法，得到下一位的进位)。</li>
* </ul>
* </li>
* <li><strong>创建新节点并连接到结果链表：</strong>
* <ul>
* <li>{@code current.next = new ListNode(sum % 10);} (当前位的数字是和的个位数)。</li>
* <li>{@code current = current.next;} (将 {@code current} 指针移动到新创建的节点)。</li>
* </ul>
* </li>
* <li><strong>移动输入链表指针：</strong>
* <ul>
* <li>{@code if (l1 != null) { l1 = l1.next; }} (如果 {@code l1} 没遍历完，就前进)。</li>
* <li>{@code if (l2 != null) { l2 = l2.next; }} (如果 {@code l2} 没遍历完，就前进)。</li>
* </ul>
* </li>
* </ol>
* </li>
* </ul>
* </li>
* <li><strong>处理最终进位：</strong>
* <ul>
* <li>当 {@code while} 循环结束后，如果 {@code carry} 仍然大于 0 (例如，{@code 5 + 5} 结果是 {@code 10}，但链表已经遍历完)，
* 需要在结果链表的末尾添加一个额外的节点来存储这个进位：
* {@code if (carry > 0) { current.next = new ListNode(carry);}}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>返回 {@code dummyHead.next}，即合并后的链表的真正头节点。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(max(M, N))}。
* <ul>
* <li>M 和 N 分别是 {@code l1} 和 {@code l2} 的长度。</li>
* <li>我们至少要遍历最长的那个链表一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(max(M, N))}。
* <ul>
* <li>新创建的链表长度最多为 {@code max(M, N) + 1} (考虑到可能多一个进位节点)。</li>
* <li>因此，空间复杂度与结果链表的长度成正比。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 创建一个虚拟头节点，便于构建结果链表
ListNode dummyHead = new ListNode(0);
// current 指针用于指向结果链表的当前末尾
ListNode current = dummyHead;
// 进位，初始为 0
int carry = 0;
// 循环直到两个链表都遍历完，并且没有进位需要处理
while (l1 != null || l2 != null) {
// 获取 l1 当前节点的值，如果 l1 为空则为 0
int val1 = (l1 != null) ? l1.val : 0;
// 获取 l2 当前节点的值，如果 l2 为空则为 0
int val2 = (l2 != null) ? l2.val : 0;
// 计算当前位的和 (包括进位)
int sum = val1 + val2 + carry;
// 计算新的进位
carry = sum / 10;
// 计算当前位要存储的数字 (和的个位数)
int digit = sum % 10;
// 创建新节点并连接到结果链表
current.next = new ListNode(digit);
// 移动 current 指针到新节点
current = current.next;
// 移动 l1 和 l2 指针
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
// 循环结束后，如果还有进位，需要添加一个新节点
if (carry > 0) {
current.next = new ListNode(carry);
}
// 返回虚拟头节点的下一个节点，即结果链表的真正头节点
return dummyHead.next;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}删除链表的倒数第 N 个结点
java
/**
* <p>此方法解决“删除链表的倒数第 N 个结点”问题，使用<strong>双指针法</strong>（快慢指针）。</p>
* <p>核心思想是：利用两个指针 {@code first} 和 {@code second}，让 {@code first} 先行 {@code n} 步，
* 然后 {@code first} 和 {@code second} 同步前进，当 {@code first} 到达链表末尾（{@code null}）时，
* {@code second} 恰好停在要删除节点的前一个位置。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(0);}。
* 虚拟头节点是为了简化特殊情况（如删除头节点）的处理。
* 它指向原始链表的头节点：{@code dummyHead.next = head;}。</li>
* </ul>
* </li>
* <li><strong>初始化双指针：</strong>
* <ul>
* <li>{@code ListNode first = dummyHead;}</li>
* <li>{@code ListNode second = dummyHead;}</li>
* <li>两个指针都从虚拟头节点开始。</li>
* </ul>
* </li>
* <li><strong>快指针先行 {@code n} 步：</strong>
* <ul>
* <li>{@code for (int i = 0; i < n; i++) { first = first.next; }}。
* 执行此步骤后，{@code first} 指针将比 {@code second} 指针（仍在 {@code dummyHead}）多走 {@code n} 步。
* 此时，{@code first} 和 {@code second} 之间相隔 {@code n} 个节点。</li>
* </ul>
* </li>
* <li><strong>快慢指针同步前进：</strong>
* <ul>
* <li>进入 {@code while (first.next != null)} 循环。
* 这个循环条件确保 {@code first} 最终会停在链表的最后一个节点，或者 {@code null}。
* 当 {@code first.next} 为 {@code null} 时，{@code first} 指针指向的是链表的最后一个节点。
* 如果 {@code first} 实际上比 {@code second} 多走了 {@code n+1} 步，那么当 {@code first} 走到 {@code null} 时，{@code second} 刚好停在要删除节点的前一个节点。
* <strong>修正：</strong> 当 {@code first.next != null} 循环结束时，{@code first} 指向的是原始链表中的<strong>最后一个节点</strong>。此时 {@code second} 指向的是<strong>要删除节点的前一个节点</strong>。</li>
* <li>在循环内部，{@code first} 和 {@code second} 同时向前移动一步：
* <ul>
* <li>{@code first = first.next;}</li>
* <li>{@code second = second.next;}</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>删除节点：</strong>
* <ul>
* <li>当 {@code while} 循环结束后，{@code second} 指针指向的是要删除的倒数第 N 个节点的前一个节点。</li>
* <li>执行删除操作：{@code second.next = second.next.next;}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>返回 {@code dummyHead.next}，即处理后的链表的头节点。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>其中 L 是链表的长度。</li>
* <li>{@code first} 指针总共遍历了 L 步（从 {@code dummyHead} 到最后一个节点）。{@code second} 指针遍历了 {@code L-n} 步。</li>
* <li>总时间复杂度只与链表长度呈线性关系。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针变量。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建一个虚拟头节点，指向原始链表的头部
// 这样可以统一处理删除头节点的情况
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// 初始化两个指针，都指向虚拟头节点
ListNode first = dummyHead;
ListNode second = dummyHead;
// first 指针先向前移动 n 步
// 这样 first 和 second 之间就相隔了 n 个节点
for (int i = 0; i < n; i++) {
first = first.next;
}
// 同时移动 first 和 second 指针，直到 first 到达链表的末尾
// 当 first.next 为 null 时，first 指向的是链表的最后一个节点
// 此时，second 指针停在要删除的倒数第 n 个节点的前一个位置
while (first.next != null) {
first = first.next;
second = second.next;
}
// 删除倒数第 n 个节点
// second.next 现在是要删除的节点
// 将 second.next 指向 second.next.next 跳过要删除的节点
second.next = second.next.next;
// 返回虚拟头节点的下一个节点，即处理后的链表的头节点
return dummyHead.next;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}两两交换链表中的节点
java
/**
* <p>此方法通过<strong>迭代法</strong>，两两交换链表中相邻的节点。</p>
* <p>核心思想是：使用一个虚拟头节点和 {@code prev} 指针来简化操作。
* {@code prev} 指针始终指向当前要交换的两个节点的前一个节点。每次迭代交换一对节点。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(0);}。它的 {@code next} 指向原始链表的头节点：{@code dummyHead.next = head;}。
* 这使得对原链表头节点的交换处理与其他节点保持一致，无需特殊判断。</li>
* </ul>
* </li>
* <li><strong>初始化 {@code prev} 指针：</strong>
* <ul>
* <li>{@code ListNode prev = dummyHead;}。
* {@code prev} 指针将始终指向已经处理完毕的子链表的末尾节点，或当前待交换对的前一个节点。</li>
* </ul>
* </li>
* <li><strong>循环处理：</strong>
* <ul>
* <li>进入 {@code while (prev.next != null && prev.next.next != null)} 循环。
* <ul>
* <li>{@code prev.next != null} 确保至少有一个节点可以作为 {@code node1}。</li>
* <li>{@code prev.next.next != null} 确保至少有两个节点可以作为 {@code node1} 和 {@code node2} 进行交换。</li>
* </ul>
* </li>
* <li>在循环内部，每次处理一对节点：
* <ol type="a">
* <li><strong>确定待交换节点：</strong>
* <ul>
* <li>{@code ListNode node1 = prev.next;} (第一个节点)。</li>
* <li>{@code ListNode node2 = node1.next;} (第二个节点)。</li>
* </ul>
* </li>
* <li><strong>执行交换操作 (重新连接指针)：</strong>
* <ul>
* <li>{@code prev.next = node2;} (将 {@code prev} 连接到交换后的新头 {@code node2})。</li>
* <li>{@code node1.next = node2.next;} (将 {@code node1} 连接到下一对的开始，因为 {@code node1} 会成为交换后的第二位)。</li>
* <li>{@code node2.next = node1;} (将 {@code node2} 连接到 {@code node1}，完成 {@code node1} 和 {@code node2} 的内部交换)。</li>
* </ul>
* </li>
* <li><strong>更新 {@code prev} 指针：</strong>
* <ul>
* <li>{@code prev = node1;} (将 {@code prev} 移动到当前已交换对的第二个节点，为下一轮循环做准备)。</li>
* </ul>
* </li>
* </ol>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>返回 {@code dummyHead.next}，即交换后的链表的头节点。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>其中 L 是链表的长度。</li>
* <li>我们遍历链表一次，每次迭代处理两个节点，因此时间复杂度与链表长度呈线性关系。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针变量 (dummyHead, prev, node1, node2)。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode swapPairs(ListNode head) {
// 创建一个虚拟头节点，它的 next 指向原始链表的头
// 这样可以简化对链表头部的操作，尤其当头节点被交换时
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// prev 指针始终指向当前正在处理的两个节点的前一个节点
ListNode prev = dummyHead;
// 循环条件：确保至少还有两个节点可以进行交换
// prev.next != null 确保有 node1
// prev.next.next != null 确保有 node2
while (prev.next != null && prev.next.next != null) {
// 确定要交换的两个节点
ListNode node1 = prev.next;
ListNode node2 = node1.next;
// 执行交换操作：重新连接指针
// 1. prev 连接到 node2
prev.next = node2;
// 2. node1 连接到 node2 后面的节点 (为下一对的开始)
node1.next = node2.next;
// 3. node2 连接到 node1 (完成 node1 和 node2 的交换)
node2.next = node1;
// 移动 prev 指针到交换后的第二个节点 (即原来的 node1)，为下一次迭代做准备
prev = node1;
}
// 返回虚拟头节点的下一个节点，即交换后的新链表的头节点
return dummyHead.next;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法通过<strong>递归法</strong>，两两交换链表中相邻的节点。</p>
* <p>核心思想是：如果链表中有足够的节点（至少两个），就交换前两个节点，
* 然后递归地对剩余链表部分（从第三个节点开始）进行同样的两两交换，
* 最后将交换后的前两个节点与递归结果连接起来。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>基本情况 (Base Cases)：</strong>
* <ul>
* <li>如果 {@code head == null} (空链表) 或者 {@code head.next == null} (只有一个节点)，
* 说明没有两对节点可以交换，直接返回 {@code head}。这是递归的终止条件。</li>
* </ul>
* </li>
* <li><strong>确定当前递归层的节点：</strong>
* <ul>
* <li>{@code ListNode firstNode = head;} (第一个节点)。</li>
* <li>{@code ListNode secondNode = head.next;} (第二个节点)。</li>
* </ul>
* </li>
* <li><strong>递归调用：</strong>
* <ul>
* <li>{@code ListNode swappedRemaining = swapPairs(secondNode.next);}
* 递归地调用 {@code swapPairs} 函数，对 {@code secondNode} 后面的链表部分进行两两交换。
* {@code swappedRemaining} 将是这部分链表交换后的新头节点。</li>
* </ul>
* </li>
* <li><strong>当前层交换与连接：</strong>
* <ul>
* <li>{@code secondNode.next = firstNode;} (将 {@code secondNode} 连接到 {@code firstNode}，完成当前层的交换)。</li>
* <li>{@code firstNode.next = swappedRemaining;} (将 {@code firstNode} 连接到递归处理后的剩余链表，将结果链表拼接起来)。</li>
* </ul>
* </li>
* <li><strong>返回当前层交换后的头节点：</strong>
* <ul>
* <li>{@code return secondNode;} (因为 {@code secondNode} 在交换后成为了当前局部子链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>其中 L 是链表的长度。</li>
* <li>每个节点只会被访问一次（在它作为 {@code head} 或 {@code nextHead} 时），并且每个节点只会进行常数次指针操作。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>这是由于递归调用栈的深度。在最坏情况下（链表没有被交换的节点，或者链表很长），
* 递归栈的深度会与链表长度 L 成正比。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode swapPairs(ListNode head) {
// 基本情况：如果链表为空或只有一个节点，无法进行两两交换，直接返回
if (head == null || head.next == null) {
return head;
}
// 确定当前需要交换的两个节点
ListNode firstNode = head;
ListNode secondNode = head.next;
// 递归地处理剩余的链表部分 (从第三个节点开始)
// secondNode.next 将指向这部分链表交换后的头节点
ListNode swappedRemaining = swapPairs(secondNode.next);
// 执行当前两个节点的交换和连接
// 1. 将 secondNode 连接到 firstNode (完成当前对的交换)
secondNode.next = firstNode;
// 2. 将 firstNode 连接到递归处理后的剩余部分
firstNode.next = swappedRemaining;
// 返回交换后的新头节点 (原来的 secondNode)
return secondNode;
}
// ListNode 类的定义 (与上面相同)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}K 个一组翻转链表
java
/**
* <p>此方法通过<strong>迭代</strong>方式，以 K 个节点为一组翻转链表。</p>
* <p>核心思想：使用一个虚拟头节点简化操作，并维护 {@code prev} 和 {@code head} 指针。
* 在主循环中，每次找到 K 个节点组成的一组，将其与前后连接断开并进行翻转，
* 然后重新连接回主链表。如果剩余节点不足 K 个，则不再翻转。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(0);}。它指向原始链表的头节点：{@code dummyHead.next = head;}。
* 这有助于统一处理链表头部的翻转情况。</li>
* </ul>
* </li>
* <li><strong>初始化 {@code prev} 指针：</strong>
* <ul>
* <li>{@code ListNode prev = dummyHead;}。{@code prev} 始终指向已处理部分的末尾节点 (一个已翻转组的尾部)。</li>
* </ul>
* </li>
* <li><strong>主循环 {@code while (head != null)}：</strong>
* <ul>
* <li>只要 {@code head} 不为空，就尝试处理下一组。</li>
* <li><strong>a. 检查是否有 {@code k} 个节点：</strong>
* <ul>
* <li>使用一个 {@code tail} 指针从 {@code prev} 开始，向前走 {@code k} 步。</li>
* <li>{@code ListNode tail = prev;}</li>
* <li>{@code for (int i = 0; i < k; i++) { tail = tail.next; if (tail == null) break; }}。</li>
* <li>如果 {@code tail} 在此过程中变为 {@code null}，说明剩余节点不足 {@code k} 个。
* 此时 {@code prev.next} 仍然指向未翻转的 {@code head}，直接跳出循环即可，剩余部分保持原样。</li>
* <li>{@code if (tail == null) break;}</li>
* </ul>
* </li>
* <li><strong>b. 记录关键节点：</strong>
* <ul>
* <li>{@code ListNode nextGroupHead = tail.next;} (保存下一组的头节点)。</li>
* <li>{@code ListNode currentGroupHead = head;} (保存当前组的原始头节点，翻转后它将变为尾节点)。</li>
* </ul>
* </li>
* <li><strong>c. 断开当前组：</strong>
* <ul>
* <li>{@code tail.next = null;} (将当前 {@code k} 组从主链表中临时断开，便于独立翻转)。</li>
* </ul>
* </li>
* <li><strong>d. 翻转当前组：</strong>
* <ul>
* <li>{@code ListNode newHead = reverse(head);} (调用辅助函数翻转 {@code currentGroupHead} 开始的链表片段，返回新的头节点)。</li>
* </ul>
* </li>
* <li><strong>e. 重新连接链表：</strong>
* <ul>
* <li>{@code prev.next = newHead;} (将前一个组的末尾连接到当前翻转组的新头)。</li>
* <li>{@code currentGroupHead.next = nextGroupHead;} (将当前翻转组的原始头节点 — 现在是尾节点 — 连接到下一组的头节点)。</li>
* </ul>
* </li>
* <li><strong>f. 更新指针为下一轮做准备：</strong>
* <ul>
* <li>{@code prev = currentGroupHead;} (现在 {@code prev} 位于当前已翻转组的末尾)。</li>
* <li>{@code head = nextGroupHead;} (现在 {@code head} 移到下一组的起点)。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return dummyHead.next;}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>辅助函数 {@code reverse(ListNode head)}：</h3>
* <p>这是一个标准的链表翻转函数，用于翻转从 {@code head} 开始到 {@code null} (因为我们已将 {@code k} 组断开) 的链表片段。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>其中 L 是链表的总长度。</li>
* <li>主循环遍历链表一次，每次迭代处理 K 个节点。每个节点会被访问常数次（查找 Kth 节点、翻转）。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针变量。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode reverseKGroup(ListNode head, int k) {
// 创建一个虚拟头节点，指向原始链表的头部
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// prev 指针始终指向当前已翻转部分（或 dummyHead）的末尾
ListNode prev = dummyHead;
// head 指针指向当前待翻转组的第一个节点
while (head != null) {
// 1. 检查当前组是否至少有 k 个节点
// tail 指针用于找到当前组的第 k 个节点 (即翻转后的新头的前一个节点)
// 这里 tail 从 prev 开始，所以它实际上是去找到当前组的最后一个节点（原链表中的第 k 个节点）
ListNode tail = prev;
for (int i = 0; i < k; i++) {
tail = tail.next;
// 如果在找到第 k 个节点之前，tail 变成了 null
// 说明剩余节点不足 k 个，不需要翻转，直接跳出循环
if (tail == null) {
return dummyHead.next; // 返回当前已构建的链表
}
}
// 2. 记录下一组的头节点
ListNode nextGroupHead = tail.next;
// 记录当前组的原始头节点（翻转后它将是尾节点）
ListNode currentGroupHead = head;
// 3. 断开当前 k 组与后续链表的连接，以便独立翻转
tail.next = null;
// 4. 翻转当前 k 组
// reverse 方法返回翻转后的新头节点
ListNode newHead = reverse(head);
// 5. 重新连接链表
// prev 的 next 指向当前翻转组的新头
prev.next = newHead;
// 当前组的原始头节点（现在是尾节点）的 next 指向下一组的头节点
currentGroupHead.next = nextGroupHead;
// 6. 更新 prev 和 head 指针，为下一轮循环做准备
prev = currentGroupHead; // prev 移动到当前已翻转组的末尾
head = nextGroupHead; // head 移动到下一组的起点
}
// 返回虚拟头节点的下一个节点，即整个链表翻转后的头节点
return dummyHead.next;
}
/**
* 辅助函数：标准的链表翻转
* 翻转从 head 开始的链表，直到其 next 为 null
*
* @param head 要翻转的链表的头节点
* @return 翻转后的链表的新头节点
*/
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 保存下一个节点
curr.next = prev; // 翻转当前节点的指向
prev = curr; // Prev 指针向前移动
curr = nextTemp; // Current 指针向前移动
}
return prev; // 返回翻转后的新头节点
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}随机链表的复制
java
/**
* <p>此方法解决“随机链表的复制”问题，使用<strong>哈希表</strong>（Map）来存储原节点到复制节点的映射关系。</p>
* <p>核心思想：分两步进行。第一步创建所有新节点并建立映射；第二步根据映射设置新节点的 {@code next} 和 {@code random} 指针。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code head == null}，直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>创建映射哈希表：</strong>
* <ul>
* <li>{@code Map<Node, Node> map = new HashMap<>();}。
* 键是原链表的节点，值是其对应的复制链表中的新节点。</li>
* </ul>
* </li>
* <li><strong>第一次遍历：创建所有新节点并建立映射。</strong>
* <ul>
* <li>{@code Node curr = head;}</li>
* <li>{@code while (curr != null)}：
* <ul>
* <li>{@code map.put(curr, new Node(curr.val));}</li>
* <li>{@code curr = curr.next;}</li>
* </ul>
* </li>
* <li>此时，所有原节点都有了对应的复制节点，但这些复制节点的 {@code next} 和 {@code random} 指针都还未设置。</li>
* </ul>
* </li>
* <li><strong>第二次遍历：设置新节点的 {@code next} 和 {@code random} 指针。</strong>
* <ul>
* <li>{@code curr = head;} (重新从原链表头部开始遍历)。</li>
* <li>{@code while (curr != null)}：
* <ul>
* <li>{@code Node copyNode = map.get(curr);} (获取当前原节点对应的复制节点)。</li>
* <li>{@code copyNode.next = map.get(curr.next);} (设置 {@code copyNode} 的 {@code next} 指针，指向 {@code curr.next} 对应的复制节点)。
* 如果 {@code curr.next} 为 {@code null}，{@code map.get(null)} 也会返回 {@code null}。</li>
* <li>{@code copyNode.random = map.get(curr.random);} (设置 {@code copyNode} 的 {@code random} 指针，指向 {@code curr.random} 对应的复制节点)。
* 如果 {@code curr.random} 为 {@code null}，{@code map.get(null)} 也会返回 {@code null}。</li>
* <li>{@code curr = curr.next;}</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return map.get(head);} (返回原链表头节点 {@code head} 对应的复制节点，即复制链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 N 是链表的长度。</li>
* <li>我们两次遍历链表，哈希表的 {@code put} 和 {@code get} 操作的平均时间复杂度是 O(1)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>哈希表会存储 N 个键值对，每个键值对都是 Node 类型的引用。</li>
* </ul>
* </li>
* </ul>
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 使用 HashMap 存储原节点到复制节点的映射
// Key: original Node, Value: copied Node
Map<Node, Node> map = new HashMap<>();
// 第一次遍历：创建所有新节点并建立映射
Node curr = head;
while (curr != null) {
map.put(curr, new Node(curr.val));
curr = curr.next;
}
// 第二次遍历：设置所有新节点的 next 和 random 指针
curr = head; // 重新从原链表头部开始
while (curr != null) {
Node copyNode = map.get(curr);
// 设置 next 指针：curr.next 对应的复制节点
copyNode.next = map.get(curr.next);
// 设置 random 指针：curr.random 对应的复制节点
copyNode.random = map.get(curr.random);
curr = curr.next;
}
// 返回复制链表的头节点（原 head 对应的复制节点）
return map.get(head);
}
// Node 类的定义 (题目给出)
static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}java
/**
* <p>此方法解决“随机链表的复制”问题，使用<strong>O(1) 额外空间</strong>的精妙方法。</p>
* <p>核心思想：通过在原链表节点之间插入复制节点、设置随机指针、最后分离链表这三步来完成深拷贝。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code head == null}，直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>第一步：在原节点后面插入复制节点（构造混合链表）。</strong>
* <ul>
* <li>遍历原始链表。对于每个原始节点 {@code curr}：
* <ul>
* <li>创建一个新的复制节点 {@code copyNode}，其值为 {@code curr.val}。</li>
* <li>将 {@code copyNode} 插入到 {@code curr} 和 {@code curr.next} 之间：
* {@code copyNode.next = curr.next;}
* {@code curr.next = copyNode;}</li>
* <li>移动 {@code curr} 到下一个原始节点 (即 {@code copyNode.next})，继续处理。
* {@code curr = copyNode.next;}</li>
* </ul>
* </li>
* <li>此时链表结构变为：{@code N1 -> N1' -> N2 -> N2' -> N3 -> N3' ...}</li>
* </ul>
* </li>
* <li><strong>第二步：设置复制节点的 {@code random} 指针。</strong>
* <ul>
* <li>再次遍历混合链表。对于每个原始节点 {@code curr}：
* <ul>
* <li>其对应的复制节点是 {@code copyNode = curr.next;}。</li>
* <li>如果 {@code curr.random} 不为 {@code null} (即原节点有随机指针指向)：
* <ul>
* <li>{@code copyNode.random} (复制节点的随机指针) 应该指向 {@code curr.random} 对应的复制节点。</li>
* <li>而 {@code curr.random} 的复制节点就是 {@code curr.random.next} (因为我们已经在前面插入了)。</li>
* <li>所以：{@code copyNode.random = curr.random.next;}</li>
* </ul>
* </li>
* <li>移动 {@code curr} 到下一个原始节点 (即 {@code copyNode.next})。
* {@code curr = copyNode.next;}</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>第三步：分离原链表和复制链表。</strong>
* <ul>
* <li>{@code curr = head;} (原始链表操作指针)。</li>
* <li>{@code Node newHead = head.next;} (复制链表的头节点)。</li>
* <li>{@code Node copyCurr = newHead;} (复制链表操作指针)。</li>
* <li>{@code while (curr != null)}：
* <ul>
* <li>将 {@code curr.next} 指向下一个原始节点：{@code curr.next = copyCurr.next;}。</li>
* <li>将 {@code copyCurr.next} 指向下一个复制节点（如果存在）：
* {@code if (copyCurr.next != null) { copyCurr.next = copyCurr.next.next; }}。</li>
* <li>移动 {@code curr} 和 {@code copyCurr} 到各自链表的下一个节点：
* {@code curr = curr.next;}
* {@code copyCurr = copyCurr.next;}</li>
* </ul>
* <p>这个循环巧妙地将 {@code 原节点.next} 从 {@code 复制节点} 指向了 {@code 下一个原节点}；
* 同时将 {@code 复制节点.next} 从 {@code 下一个原节点} 指向了 {@code 下一个复制节点}。</p>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return newHead;} (返回分离后的复制链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 N 是链表的长度。</li>
* <li>我们三次遍历链表，每次遍历都是线性的。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>除了存储新链表所需的空间，我们没有使用任何额外的辅助数据结构（如哈希表）。</li>
* </ul>
* </li>
* </ul>
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步：在每个原始节点后面插入其复制节点
// 链表变为：N1 -> N1' -> N2 -> N2' -> N3 -> N3' ...
Node curr = head;
while (curr != null) {
Node copyNode = new Node(curr.val);
copyNode.next = curr.next;
curr.next = copyNode;
curr = copyNode.next; // 移动到下一个原始节点
}
// 第二步：设置复制节点的 random 指针
// N1'.random 应该指向 N1.random 的复制节点 (N1.random.next)
curr = head;
while (curr != null) {
Node copyNode = curr.next;
if (curr.random != null) {
copyNode.random = curr.random.next; // curr.random.next 是 curr.random 的复制节点
}
curr = copyNode.next; // 移动到下一个原始节点
}
// 第三步：分离原始链表和复制链表
Node newHead = head.next; // 复制链表的头节点
curr = head; // 遍历原始链表的节点
Node copyCurr = newHead; // 遍历复制链表的节点
while (curr != null) {
// 还原原始链表的下一个指针
curr.next = copyCurr.next;
// 设置复制链表 copyCurr 的 next 指针
// 如果 copyCurr.next 不是空值，则它指向下一个原始节点（例如 N2）
// 然后 copyCurr.next.next 才指向下一个复制节点（例如 N2')
if (copyCurr.next != null) {
copyCurr.next = copyCurr.next.next;
}
// 移动 curr 和 copyCurr 到各自链表的下一个节点
curr = curr.next;
copyCurr = copyCurr.next;
}
return newHead;
}
// Node 类的定义 (题目给出)
static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}排序链表
java
/**
* <p>此方法解决“排序链表”问题，采用<strong>归并排序 (Merge Sort)</strong> 算法。</p>
* <p>归并排序特别适合链表，因为它只需要线性遍历和指针重新连接，避免了链表随机访问效率低的问题。</p>
*
* <h3>核心思想：</h3>
* <ol>
* <li><strong>分 (Divide)：</strong> 递归地将链表分成两半。</li>
* <li><strong>治 (Conquer)：</strong> 独立地对这两半进行排序。</li>
* <li><strong>合 (Combine)：</strong> 将两个已排序的子链表合并成一个完整的已排序链表。</li>
* </ol>
*
* <h3>{@code sortList(head)} 函数步骤：</h3>
* <ol>
* <li><strong>基本情况 (Base Case)：</strong>
* <ul>
* <li>如果链表为空 ({@code head == null}) 或只有一个节点 ({@code head.next == null})，则它已经是有序的，直接返回 {@code head}。</li>
* </ul>
* </li>
* <li><strong>分治 - 寻找中点并断开链表：</strong>
* <ul>
* <li>使用快慢指针法寻找链表的中点。
* <ul>
* <li>{@code slow} 指针每次走一步。</li>
* <li>{@code fast} 指针每次走两步。</li>
* <li>{@code prev} 指针始终指向 {@code slow} 的前一个节点，用于在中点处断开链表。</li>
* </ul>
* </li>
* <li>当 {@code fast} 走到链表末尾时，{@code slow} 恰好位于链表的中点。</li>
* <li>{@code prev.next = null;} 从中点处断开链表，将其分为两半。</li>
* </ul>
* </li>
* <li><strong>递归排序两半：</strong>
* <ul>
* <li>{@code ListNode list1 = sortList(head);} (对前半部分链表递归排序)。</li>
* <li>{@code ListNode list2 = sortList(slow);} (对后半部分链表递归排序)。</li>
* </ul>
* </li>
* <li><strong>合并有序链表：</strong>
* <ul>
* <li>{@code return mergeTwoLists(list1, list2);} (调用辅助函数将两半合并成一个有序链表)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>{@code mergeTwoLists(l1, l2)} 辅助函数步骤：</h3>
* <ol>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(0);}。用于简化合并操作，避免对头节点的特殊处理。</li>
* <li>{@code ListNode curr = dummyHead;}。{@code curr} 指针用于构建合并后的链表。</li>
* </ul>
* </li>
* <li><strong>遍历合并：</strong>
* <ul>
* <li>{@code while (l1 != null && l2 != null)}：
* <ul>
* <li>比较 {@code l1.val} 和 {@code l2.val}。</li>
* <li>将值较小的节点连接到 {@code curr.next}。</li>
* <li>将 {@code curr} 移动到新连接的节点。</li>
* <li>将对应子链表的指针 ({@code l1} 或 {@code l2}) 移到下一个节点。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>处理剩余部分：</strong>
* <ul>
* <li>{@code if (l1 != null) { curr.next = l1; }} (如果 {@code l1} 还有剩余节点，直接将其连接到合并链表末尾)。</li>
* <li>{@code if (l2 != null) { curr.next = l2; }} (如果 {@code l2} 还有剩余节点，直接将其连接到合并链表末尾)。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return dummyHead.next;} (返回合并后的链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N log N)}。
* <ul>
* <li>每次递归调用，我们将链表分成两半 ({@code log N} 层递归)。</li>
* <li>每一层递归，我们需要 O(N) 的时间来合并子链表（{@code mergeTwoLists} 操作）。</li>
* <li>因此总时间复杂度为 O(N log N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(log N)}。
* <ul>
* <li>这是递归调用栈的深度。在最坏情况下（链表长度），递归栈的深度为 {@code log N}。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode sortList(ListNode head) {
// 基本情况：如果链表为空或只有一个节点，则它已经有序
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针法寻找链表的中点
// prev 指针用于在中点处断开链表，所以它要比 slow 慢一步
ListNode slow = head;
ListNode fast = head;
ListNode prev = null; // 用于记录 slow 的前一个节点
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// 从中点处断开链表
// prev.next 此时指向 slow，将其设为 null 即可断开
prev.next = null;
// 递归排序前半部分和后半部分
ListNode list1 = sortList(head); // head 是前半部分的头
ListNode list2 = sortList(slow); // slow 是后半部分的头
// 合并两个已排序的子链表
return mergeTwoLists(list1, list2);
}
/**
* 辅助函数：合并两个有序链表
*
* @param l1 第一个有序链表的头节点
* @param l2 第二个有序链表的头节点
* @return 合并后的有序链表的头节点
*/
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0); // 虚拟头节点，简化操作
ListNode curr = dummyHead; // 用于构建合并链表的指针
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 指针
}
// 将剩余的节点直接连接到合并链表的末尾
if (l1 != null) {
curr.next = l1;
} else if (l2 != null) {
curr.next = l2;
}
return dummyHead.next; // 返回合并后的链表的头节点
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法解决“排序链表”问题，采用<strong>迭代归并排序 (Bottom-Up Merge Sort)</strong> 算法，
* 实现了 <strong>O(1) 额外空间复杂度</strong>。</p>
* <p>核心思想：通过迭代的方式，从合并长度为 1 的子链表开始，逐步扩大合并的子链表长度，
* 直到整个链表有序。这种方式避免了递归栈的开销。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果链表为空 ({@code head == null}) 或只有一个节点 ({@code head.next == null})，直接返回 {@code head}。</li>
* </ul>
* </li>
* <li><strong>计算链表长度 {@code n}：</strong>
* <ul>
* <li>遍历链表一次，获取其总长度，这是迭代归并排序所需的。</li>
* </ul>
* </li>
* <li><strong>创建虚拟头节点：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(0);}。它的 {@code next} 指向原始链表的 {@code head}。它简化了头部操作。</li>
* </ul>
* </li>
* <li><strong>外层循环 (控制子链表长度 {@code subLen})：</strong>
* <ul>
* <li>{@code for (int subLen = 1; subLen < n; subLen <<= 1)}：
* <ul>
* <li>{@code subLen} 从 1 开始，每次加倍 ({@code 1, 2, 4, 8, ...})，直到大于等于链表总长度 {@code n}。</li>
* <li>{@code subLen <<= 1} 是 {@code subLen = subLen * 2} 的位运算形式。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>内层循环 (遍历链表并合并相邻子链表)：</strong>
* <ul>
* <li>{@code ListNode curr = dummyHead.next;} (每次 {@code subLen} 变化后，从混合链表的当前头开始处理)。</li>
* <li>{@code ListNode prev = dummyHead;} (指向已合并部分的末尾，用于将新的合并结果连接回主链表)。</li>
* <li>{@code while (curr != null)}：
* <ul>
* <li><strong>a. 截取第一个子链表 ({@code head1})：</strong>
* <ul>
* <li>{@code head1 = curr;}</li>
* <li>{@code ListNode head1End = head1;}</li>
* <li>{@code for (int i = 1; i < subLen && head1End != null; i++) { head1End = head1End.next; }} (找到 {@code head1} 长度为 {@code subLen} 的末尾)。</li>
* <li>如果 {@code head1End == null}，说明剩余节点不足 {@code subLen}，直接将 {@code prev.next} 连接到 {@code head1}，并跳出内层循环 (不需要再合并了)。
* {@code if (head1End == null) { prev.next = head1; break; }}</li>
* <li>{@code ListNode head2 = head1End.next;} (获取第二个子链表的头)。</li>
* <li>{@code head1End.next = null;} (断开第一个子链表，使其独立)。</li>
* </ul>
* </li>
* <li><strong>b. 截取第二个子链表 ({@code head2})：</strong>
* <ul>
* <li>{@code ListNode head2End = head2;}</li>
* <li>{@code for (int i = 1; i < subLen && head2End != null; i++) { head2End = head2End.next; }} (找到 {@code head2} 长度为 {@code subLen} 的末尾)。</li>
* <li>{@code ListNode nextGroupHead = null;} (保存下一组的头节点)。</li>
* <li>如果 {@code head2End != null}，{@code nextGroupHead = head2End.next;} 并且 {@code head2End.next = null;} (断开第二个子链表)。</li>
* </ul>
* </li>
* <li><strong>c. 合并两个子链表：</strong>
* <ul>
* <li>{@code ListNode mergedHead = mergeTwoLists(head1, head2);} (调用辅助函数合并 {@code head1} 和 {@code head2})。</li>
* </ul>
* </li>
* <li><strong>d. 连接到主链表并更新指针：</strong>
* <ul>
* <li>{@code prev.next = mergedHead;} (将合并后的链表连接到前一个已处理部分的末尾)。</li>
* <li>找到 {@code mergedHead} 的尾部：{@code ListNode temp = mergedHead; while (temp.next != null) { temp = temp.next; }}。</li>
* <li>{@code prev = temp;} (更新 {@code prev} 指针到当前合并部分的尾部)。</li>
* <li>{@code curr = nextGroupHead;} (将 {@code curr} 移动到下一个待处理的 {@code 2 * subLen} 组的起点)。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return dummyHead.next;} (返回排序后的链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>{@code mergeTwoLists(l1, l2)} 辅助函数：</h3>
* <p>与递归归并排序中的实现完全相同，用于合并两个有序链表。它是 O(N) 时间和 O(1) 空间的。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N log N)}。
* <ul>
* <li>总长度 {@code n}，每次 {@code subLen} 翻倍，{@code log N} 次外层循环。</li>
* <li>每次外层循环，内层循环会遍历整个链表进行合并操作，总共 {@code O(N)}。</li>
* <li>所以总时间复杂度为 O(N log N)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>只使用了常数个额外指针变量，没有递归栈或额外的数据结构。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode sortList(ListNode head) {
// 基本情况：如果链表为空或只有一个节点，则它已经有序
if (head == null || head.next == null) {
return head;
}
// 计算链表的总长度 n
int n = 0;
ListNode curr = head;
while (curr != null) {
n++;
curr = curr.next;
}
// 创建一个虚拟头节点，简化操作
// dummyHead -> 节点 1 -> 节点 2 -> ...
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// 外层循环：subLen 从 1 开始，每次翻倍 (1, 2, 4, ...)
// subLen 代表每次合并的子链表的长度
for (int subLen = 1; subLen < n; subLen <<= 1) { // 等同于 subLen = subLen * 2
curr = dummyHead.next; // curr 指向当前要处理的子链表的起点
ListNode prev = dummyHead; // prev 指向已经合并好的链表的尾部
// 内层循环：遍历整个链表，每次合并两个长度为 subLen 的子链表
while (curr != null) {
// 1. 截取第一个子链表 (head1)
ListNode head1 = curr;
ListNode head1End = head1;
for (int i = 1; i < subLen && head1End != null; i++) {
head1End = head1End.next;
}
// 如果第一个子链表不足 subLen 长度（或整个链表不足 subLen）
// 说明这一轮已经不需要再合并了，直接将剩余部分连接到 prev 后即可
if (head1End == null) {
prev.next = head1;
break;
}
// 2. 截取第二个子链表 (head2)
ListNode head2 = head1End.next; // head2 是 head1End 的下一个节点
head1End.next = null; // 断开 head1 与 head2 的连接
ListNode head2End = head2;
for (int i = 1; i < subLen && head2End != null; i++) {
head2End = head2End.next;
}
// 3. 记录下一组的起点 (nextGroupHead)
ListNode nextGroupHead = null;
if (head2End != null) {
nextGroupHead = head2End.next; // nextGroupHead 是 head2End 的下一个节点
head2End.next = null; // 断开 head2 与下一组的连接
}
// 4. 合并 head1 和 head2
ListNode mergedHead = mergeTwoLists(head1, head2);
// 5. 将合并后的链表连接到 prev
prev.next = mergedHead;
// 6. 移动 prev 到当前合并组的尾部，curr 到下一组的起点
// 找到合并后链表的尾部
ListNode temp = mergedHead;
while (temp.next != null) {
temp = temp.next;
}
prev = temp; // prev 移动到当前 merged 组的尾部
curr = nextGroupHead; // curr 移动到下一组的起点
}
}
return dummyHead.next; // 返回排序后的链表的头节点
}
/**
* 辅助函数：合并两个有序链表
* 这个函数和递归归并排序中的 mergeTwoLists 相同
*
* @param l1 第一个有序链表的头节点
* @param l2 第二个有序链表的头节点
* @return 合并后的有序链表的头节点
*/
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;
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;
}
if (l1 != null) {
curr.next = l1;
} else if (l2 != null) {
curr.next = l2;
}
return dummyHead.next;
}
// ListNode 类的定义 (通常是给定的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}合并 K 个升序链表
java
/**
* <p>此方法解决“合并 K 个升序链表”问题，采用<strong>分治法 (Divide and Conquer)</strong>。</p>
* <p>核心思想：将 K 个链表递归地分成两半，分别合并这两半，然后将合并后的两个大链表再次合并。</p>
* <p>这类似于归并排序中的合并步骤，效率优于简单的两两顺序合并。</p>
*
* <h3>{@code mergeKLists(lists)} 函数步骤 (主入口)：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果输入链表数组 {@code lists} 为 {@code null} 或长度为 {@code 0}，则没有链表可合并，直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>启动分治：</strong>
* <ul>
* <li>调用辅助函数 {@code mergeKListsDivideAndConquer}，传入链表数组以及整个数组的范围 {@code (0, lists.length - 1)}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>{@code mergeKListsDivideAndConquer(lists, start, end)} 辅助函数步骤 (递归分治)：</h3>
* <ol>
* <li><strong>基本情况 (Base Case)：</strong>
* <ul>
* <li>如果 {@code start == end}：表示只剩下一个链表，它本身就是合并结果，直接返回 {@code lists[start]}。</li>
* <li>如果 {@code start > end}：表示范围无效（例如，空数组或已处理完），返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>分治 (Divide)：</strong>
* <ul>
* <li>计算中间索引 {@code mid = start + (end - start) / 2;}。</li>
* <li>递归地合并前半部分链表：{@code ListNode list1 = mergeKListsDivideAndConquer(lists, start, mid);}。</li>
* <li>递归地合并后半部分链表：{@code ListNode list2 = mergeKListsDivideAndConquer(lists, mid + 1, end);}。</li>
* </ul>
* </li>
* <li><strong>合并 (Combine)：</strong>
* <ul>
* <li>调用 {@code mergeTwoLists} 辅助函数，将 {@code list1} 和 {@code list2} (它们都是各自子问题的合并结果，即已排序链表) 合并成一个大的有序链表。</li>
* <li>{@code return mergeTwoLists(list1, list2);}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>{@code mergeTwoLists(l1, l2)} 辅助函数 (合并两个有序链表)：</h3>
* <p>与之前问题（例如，力扣 21. 合并两个有序链表）中的实现相同。</p>
* <ol>
* <li><strong>创建虚拟头节点：</strong> {@code ListNode dummyHead = new ListNode(-1);}。</li>
* <li><strong>遍历合并：</strong> 使用 {@code curr} 指针从 {@code dummyHead} 开始，依次比较 {@code l1.val} 和 {@code l2.val}，将较小者接到 {@code curr.next}。</li>
* <li><strong>处理剩余部分：</strong> 当一个链表遍历完后，将另一个链表的剩余部分直接接到 {@code curr.next}。</li>
* <li><strong>返回结果：</strong> {@code dummyHead.next}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N log K)}。
* <ul>
* <li>其中 {@code N} 是所有链表中节点的总数。{@code K} 是链表的数量。</li>
* <li>分治将问题分解 {@code log K} 层。在每一层，我们都需要合并总共 {@code N} 个节点。</li>
* <li>例如，最底层合并 {@code K/2} 对链表，每对合并的节点总数是其长度和，所有对的总和为 {@code N}。</li>
* <li>第二层合并 {@code K/4} 对链表，每对合并的节点总数也是其长度和，所有对的总和仍为 {@code N}。</li>
* <li>因此，总时间复杂度为 {@code N * log K}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(log K)}。
* <ul>
* <li>这是递归调用栈的深度。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode mergeKLists(ListNode[] lists) {
// 如果链表数组为空或没有链表，直接返回 null
if (lists == null || lists.length == 0) {
return null;
}
// 调用分治辅助函数进行合并
return mergeKListsDivideAndConquer(lists, 0, lists.length - 1);
}
/**
* 分治法辅助函数：递归地合并指定范围内的链表
*
* @param lists 链表数组
* @param start 数组的起始索引
* @param end 数组的结束索引
* @return 合并后的链表头节点
*/
private ListNode mergeKListsDivideAndConquer(ListNode[] lists, int start, int end) {
// 基本情况：如果只剩一个链表，直接返回
if (start == end) {
return lists[start];
}
// 基本情况：如果范围无效 (start > end)，返回 null
if (start > end) {
return null;
}
// 分治：将链表数组分成两半
int mid = start + (end - start) / 2;
// 递归合并左半部分
ListNode list1 = mergeKListsDivideAndConquer(lists, start, mid);
// 递归合并右半部分
ListNode list2 = mergeKListsDivideAndConquer(lists, mid + 1, end);
// 合并两个已排序的链表
return mergeTwoLists(list1, list2);
}
/**
* 辅助函数：合并两个有序链表 (与 LeetCode 21 题相同)
*
* @param l1 第一个有序链表
* @param l2 第二个有序链表
* @return 合并后的有序链表头节点
*/
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1); // 虚拟头节点
ListNode curr = dummyHead;
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;
}
// 将剩余未合并的部分连接到末尾
if (l1 != null) {
curr.next = l1;
} else if (l2 != null) {
curr.next = l2;
}
return dummyHead.next; // 返回合并链表的头节点
}
// ListNode 类的定义 (通常是题目提供的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}java
/**
* <p>此方法解决“合并 K 个升序链表”问题，采用<strong>最小优先队列 (Min-Priority Queue / Min-Heap)</strong>。</p>
* <p>核心思想：使用优先队列动态维护所有链表当前未被合并的头节点，每次取出最小的节点，并将其所在链表的下一个节点加入队列。</p>
* <p>这是解决此类问题的最常用且高效的方法之一。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果输入链表数组 {@code lists} 为 {@code null} 或长度为 {@code 0}，则直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>创建最小优先队列：</strong>
* <ul>
* <li>{@code PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);}</li>
* <li>队列中存储 {@code ListNode} 对象，并根据它们的 {@code val} 进行升序排序（小顶堆）。</li>
* </ul>
* </li>
* <li><strong>初始化优先队列：</strong>
* <ul>
* <li>遍历 {@code lists} 数组。将每个链表的<strong>头节点</strong>（如果非空）加入到 {@code minHeap} 中。</li>
* <li>{@code for (ListNode list : lists) { if (list != null) { minHeap.add(list); } }}。</li>
* </ul>
* </li>
* <li><strong>构建结果链表：</strong>
* <ul>
* <li>{@code ListNode dummyHead = new ListNode(-1);} (虚拟头节点，便于操作)。</li>
* <li>{@code ListNode curr = dummyHead;} (用于构建合并后链表的当前指针)。</li>
* </ul>
* </li>
* <li><strong>循环处理优先队列：</strong>
* <ul>
* <li>{@code while (!minHeap.isEmpty())}：
* <ul>
* <li>{@code ListNode smallest = minHeap.poll();} (从优先队列中取出值最小的节点，这是当前所有链表中最小的节点)。</li>
* <li>{@code curr.next = smallest;} (将该最小节点连接到结果链表)。</li>
* <li>{@code curr = curr.next;} (移动结果链表的当前指针)。</li>
* <li>{@code if (smallest.next != null)}：
* <ul>
* <li>如果刚取出的节点 {@code smallest} 所属的链表还有下一个节点，则将该下一个节点加入到 {@code minHeap} 中。
* ({@code minHeap.add(smallest.next);})</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>{@code return dummyHead.next;} (返回合并后的链表的头节点)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N log K)}。
* <ul>
* <li>其中 {@code N} 是所有链表中节点的总数。{@code K} 是链表的数量。</li>
* <li><strong>初始化堆：</strong> 最多添加 {@code K} 个节点，每次添加操作的平均时间复杂度是 {@code O(log K)}。所以初始化是 {@code O(K log K)}。</li>
* <li><strong>主循环：</strong> 循环总共会执行 {@code N} 次（因为每个节点都会被取出一次）。每次循环中：
* <ul>
* <li>{@code minHeap.poll()} 操作的时间复杂度是 {@code O(log K)}。</li>
* <li>{@code minHeap.add()} 操作的时间复杂度是 {@code O(log K)}。</li>
* </ul>
* </li>
* <li>因此，总时间复杂度为 {@code O(K log K + N log K)}。由于 {@code N} 通常远大于 {@code K}，所以简化为 {@code O(N log K)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(K)}。
* <ul>
* <li>优先队列中最多会存储 {@code K} 个节点（每个链表最多有一个节点在队列中）。</li>
* </ul>
* </li>
* </ul>
*/
public ListNode mergeKLists(ListNode[] lists) {
// 如果链表数组为空或没有链表，直接返回 null
if (lists == null || lists.length == 0) {
return null;
}
// 创建一个最小优先队列
// 比较器 (a, b) -> a.val - b.val 使得队列按节点值升序排列
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
// 将所有链表的头节点（如果非空）加入到优先队列中
for (ListNode list : lists) {
if (list != null) {
minHeap.add(list);
}
}
// 创建一个虚拟头节点，用于构建合并后的链表
ListNode dummyHead = new ListNode(-1);
ListNode curr = dummyHead; // 当前构建链表的指针
// 当优先队列不为空时，不断取出最小节点并处理
while (!minHeap.isEmpty()) {
// 取出堆顶的最小节点
ListNode smallest = minHeap.poll();
// 将最小节点连接到结果链表的末尾
curr.next = smallest;
// 移动 curr 指针
curr = curr.next;
// 如果取出的节点所属的链表还有下一个节点，将其加入到优先队列中
if (smallest.next != null) {
minHeap.add(smallest.next);
}
}
// 返回合并后的链表的头节点 (跳过虚拟头节点)
return dummyHead.next;
}
// ListNode 类的定义 (通常是题目提供的)
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}LRU 缓存
java
import java.util.HashMap;
import java.util.Map;
/**
* <p>LRU 缓存 (Least Recently Used Cache) 的设计与实现。</p>
* <p>这个数据结构的核心思想是<strong>哈希表 (HashMap) + 双向链表 (Doubly Linked List)</strong>。</p>
*
* <ul>
* <li><strong>HashMap:</strong> 负责 {@code O(1)} 时间复杂度的查找、插入和删除操作。它将 {@code key} 映射到双向链表中的 {@code Node}。</li>
* <li><strong>Doubly Linked List:</strong> 负责维护元素的访问顺序，并支持 {@code O(1)} 时间复杂度的添加、删除和移动节点。
* <ul>
* <li>链表头部 (靠近 {@code head} 虚拟节点) 存放<strong>最近使用</strong>的元素。</li>
* <li>链表尾部 (靠近 {@code tail} 虚拟节点) 存放<strong>最久未使用</strong>的元素。</li>
* <li>插入新元素或访问已有元素时，将其移动到链表头部。</li>
* <li>当缓存容量不足时，淘汰链表尾部的元素。</li>
* </ul>
* </li>
* </ul>
*/
public class LRUCache {
// Node 内部类，表示双向链表中的一个节点
class Node {
int key;
int value;
Node prev;
Node next;
public Node() { // 用于创建虚拟头尾节点
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, Node> cacheMap; // 哈希表，存储 key 到 Node 的映射
private Node head; // 虚拟头节点
private Node tail; // 虚拟尾节点
private int capacity; // 缓存的最大容量
private int size; // 当前缓存中的元素数量
/**
* LRUCache 构造函数
*
* @param capacity 缓存容量 (正整数)
*/
public LRUCache(int capacity) {
this.cacheMap = new HashMap<>();
this.capacity = capacity;
this.size = 0;
// 初始化虚拟头尾节点，并相互连接
// head <-> tail
this.head = new Node();
this.tail = new Node();
head.next = tail;
tail.prev = head;
}
/**
* 获取缓存中 key 对应的值。
* 如果 key 存在，则返回其值，并将其移动到链表头部 (最近使用)。
* 否则，返回 -1。
*
* @param key 关键字
* @return 关键字的值，如果不存在则为 -1
* 时间复杂度：O(1)
*/
public int get(int key) {
Node node = cacheMap.get(key);
if (node == null) {
return -1; // key 不存在
}
// key 存在，将其移动到链表头部 (表示最近使用)
moveToHead(node);
return node.value;
}
/**
* 写入或更新缓存中的 key-value 对。
* 如果 key 已存在，则更新其值，并将其移动到链表头部。
* 如果 key 不存在：
* 1. 插入新的 key-value 对到链表头部和哈希表。
* 2. 如果缓存已满，则淘汰最久未使用的元素 (链表尾部元素)。
*
* @param key 关键字
* @param value 值
* 时间复杂度：O(1)
*/
public void put(int key, int value) {
Node node = cacheMap.get(key);
if (node != null) {
// key 已存在，更新值并移动到头部
node.value = value;
moveToHead(node);
} else {
// key 不存在
Node newNode = new Node(key, value);
// 检查缓存是否已满
if (size == capacity) {
// 缓存已满，淘汰最久未使用的节点 (链表尾部节点)
Node removedTailNode = removeTail();
cacheMap.remove(removedTailNode.key); // 从哈希表中移除
size--; // 更新大小
}
// 添加新节点到链表头部和哈希表
addToHead(newNode);
cacheMap.put(key, newNode);
size++; // 更新大小
}
}
/**
* 将指定节点移动到链表头部 (最近使用)。
* 此操作包含两步：先从原位置删除，再添加到头部。
*
* @param node 要移动的节点
* 时间复杂度：O(1)
*/
private void moveToHead(Node node) {
removeNode(node); // 从链表中删除当前节点
addToHead(node); // 将节点添加到链表头部
}
/**
* 从链表中删除指定节点。
*
* @param node 要删除的节点
* 时间复杂度：O(1)
*/
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
// 清除 node 的 prev 和 next 指针，有助于垃圾回收但不是必须的
node.prev = null;
node.next = null;
}
/**
* 将节点添加到链表头部 (在虚拟头节点 head 之后)。
*
* @param node 要添加的节点
* 时间复杂度：O(1)
*/
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 删除链表尾部的节点 (最久未使用的节点，在虚拟尾节点 tail 之前)。
*
* @return 被删除的节点
* 时间复杂度：O(1)
*/
private Node removeTail() {
Node realTail = tail.prev; // 获取真正的尾部节点
removeNode(realTail); // 删除它
return realTail;
}
}贡献者
LI SIR