00:00:00
链表
相交链表
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>**注意：** 此时 {@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} 指向的是原始链表中的**最后一个节点**。此时 {@code second} 指向的是**要删除节点的前一个节点**。</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
/**
* TODO
*/排序链表
java
/**
* TODO
*/合并 K 个升序链表
java
/**
* TODO
*/LRU 缓存
java
/**
* TODO
*/
评论