数据结构（六）

数组（Array）：核心操作与性能优化

数组是一种线性表数据结构，它使用连续的内存空间来存储相同类型的数据。数组的核心优势在于支持随机访问（通过下标直接访问元素），时间复杂度为O(1)，但插入和删除操作效率较低，尤其是在数组中间或头部操作时。

基础增删改查的实现

添加与删除逻辑

添加操作的本质是将目标位置及后续的所有元素整体后移，为新元素腾出空间，然后在指定位置插入新元素。

操作逻辑：

1. 判断插入位置的合法性（如是否越界）。
2. 从插入位置开始，将每个元素向后移动一位（需从后往前遍历，避免数据覆盖）。
3. 在插入位置放入新元素。

时间复杂度：O(n)（需要移动n个元素，n为数组长度）。

代码示例（Java）：

public class ArrayOperations { // 添加元素到数组指定位置 public int[] addElement(int[] arr, int index, int value) { // 检查数组是否已满（此处简化处理，假设传入的是可扩展的数组，实际开发中可使用动态数组） if (arr.length == 0) { return new int[]{value}; } // 创建新数组，长度+1 int[] newArr = new int[arr.length + 1]; // 复制插入位置之前的元素 System.arraycopy(arr, 0, newArr, 0, index); // 放入新元素 newArr[index] = value; // 复制插入位置之后的元素 System.arraycopy(arr, index, newArr, index + 1, arr.length - index); return newArr; } public static void main(String[] args) { ArrayOperations op = new ArrayOperations(); int[] arr = {1, 2, 3, 4, 5}; int[] newArr = op.addElement(arr, 2, 10); // 在索引2位置插入10 System.out.println(Arrays.toString(newArr)); // 输出：[1, 2, 10, 3, 4, 5] } }

删除操作的本质是通过数据覆盖实现，核心是避免频繁移动数据，可通过双指针（快慢指针）实现原地删除，提升效率。

传统删除问题：直接删除指定位置元素后，需要将后续元素前移，仍会导致O(n)的移动开销。

双指针优化：使用快指针（fast）遍历数组，慢指针（slow）记录有效元素的位置。快指针跳过需要删除的元素，慢指针实时更新有效元素的位置，最终将慢指针长度作为新数组长度，实现原地删除。

代码示例（双指针删除指定值的元素）：

public class ArrayDeleteWithTwoPointers { // 原地删除数组中值为target的元素，返回删除后数组的长度 public int removeElement(int[] nums, int target) { int slow = 0; // 慢指针，指向下一个有效元素的位置 for (int fast = 0; fast < nums.length; fast++) { // 快指针遍历数组 // 如果快指针指向的元素不是目标值，将其赋值给慢指针位置 if (nums[fast] != target) { nums[slow] = nums[fast]; slow++; } } return slow; // 慢指针的值即为删除后的有效长度 } public static void main(String[] args) { ArrayDeleteWithTwoPointers op = new ArrayDeleteWithTwoPointers(); int[] nums = {3, 2, 2, 3, 4}; int newLength = op.removeElement(nums, 3); // 删除所有值为3的元素 System.out.println("删除后数组长度：" + newLength); // 输出：3 // 打印有效元素（长度为newLength） for (int i = 0; i < newLength; i++) { System.out.print(nums[i] + " "); // 输出：2 2 4 } } }

核心要点：双指针删除的本质是用慢指针压缩有效数据范围，避免了后续元素的批量移动，同时不依赖额外空间，是数组删除操作的高效优化方案。

查找与修改

查找操作：无序数组的查找只能通过遍历实现，逐个比对元素，直到找到目标值或遍历完成。

时间复杂度：O(n)（最坏情况下需要遍历所有元素）。

实现逻辑：遍历数组，判断当前元素是否为目标值，找到则返回下标，否则继续遍历，遍历完未找到返回-1。

代码示例：

public class ArrayFind { // 在无序数组中查找目标值的下标，不存在则返回-1 public int findIndex(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; } public static void main(String[] args) { ArrayFind op = new ArrayFind(); int[] arr = {5, 3, 8, 1, 9}; int index = op.findIndex(arr, 1); // 查找值为1的元素 System.out.println("元素1的下标：" + index); // 输出：3 } }

修改操作：数组支持随机访问，可直接通过下标定位元素并覆盖，时间复杂度为O(1)；若需通过条件定位修改，则需遍历，时间复杂度为O(n)。

直接下标修改：arr[index] = newValue，直接覆盖目标位置元素。

条件遍历修改：遍历数组，找到满足条件的元素，进行修改。

代码示例：

public class ArrayModify { // 通过下标直接修改元素 public void modifyByIndex(int[] arr, int index, int newValue) { if (index >= 0 && index < arr.length) { arr[index] = newValue; } } // 修改所有值为target的元素为newValue public void modifyByCondition(int[] arr, int target, int newValue) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { arr[i] = newValue; } } } public static void main(String[] args) { ArrayModify op = new ArrayModify(); int[] arr = {2, 5, 2, 7, 3}; op.modifyByIndex(arr, 1, 10); // 修改索引1的元素为10 op.modifyByCondition(arr, 2, 20); // 将所有值为2的元素修改为20 System.out.println(Arrays.toString(arr)); // 输出：[20, 10, 20, 7, 3] } }

有序数组的算法优化

当数组是有序的（如升序、降序），我们可以利用其有序性对核心操作进行算法优化，显著降低时间复杂度，其中最核心的优化是二分查找法，以及基于有序性的高效插入策略。

二分查找法（Binary Search）

核心原理：利用数组的有序性，每次通过中间元素将查找区间缩小一半，快速定位目标元素，将查找时间复杂度从O(n)降至O(log n)，是有序数组查找的最优算法。

关键要素：
三个核心指针：left（左边界）、right（右边界）、mid（中间位置，mid = left + (right - left) / 2，避免整数溢出）。
循环终止条件：left <= right（确保区间内存在元素时才进行查找）。
指针移动规则：根据中间元素与目标值的比较结果，缩小查找区间（target < nums[mid]则right = mid - 1；target > nums[mid]则left = mid + 1），避免死循环和数据遗漏。

插入与遍历操作

尾插法（追加到链表末尾）

尾插法将新节点添加到链表末尾，需先遍历到最后一个节点，再修改其next指针指向新节点。

// 尾插法示例 public ListNode appendNode(ListNode head, int value) { ListNode newNode = new ListNode(value); if (head == null) { return newNode; // 若链表为空，新节点即为头节点 } ListNode current = head; while (current.next != null) { current = current.next; // 遍历到最后一个节点 } current.next = newNode; // 将新节点链接到末尾 return head; }

头插法（插入到链表头部）

头插法将新节点插入到链表头部，新节点的next指向原头节点，并更新头节点引用。

// 头插法示例 public ListNode prependNode(ListNode head, int value) { ListNode newNode = new ListNode(value); newNode.next = head; // 新节点指向原头节点 return newNode; // 返回新头节点 }

任意位置插入

在指定位置插入新节点，需先定位插入位置的前驱节点，再调整指针指向。

// 在指定位置插入节点 public ListNode insertAtPosition(ListNode head, int value, int position) { if (position <= 0) { return prependNode(head, value); // 位置≤0视为头插 } ListNode newNode = new ListNode(value); ListNode current = head; for (int i = 0; i < position - 1 && current != null; i++) { current = current.next; // 移动到插入位置的前驱节点 } if (current == null) { return appendNode(head, value); // 位置超范围则尾插 } newNode.next = current.next; current.next = newNode; return head; }

遍历操作

遍历链表时从头节点开始，依次访问每个节点的值，直到遇到null。

// 遍历链表并打印节点值 public void traverseList(ListNode head) { ListNode current = head; while (current != null) { System.out.print(current.value + " -> "); current = current.next; } System.out.println("null"); }

删除操作

删除节点需定位目标节点的前驱节点，修改其next指针跳过目标节点。

// 删除指定值的节点（首次出现） public ListNode deleteNode(ListNode head, int value) { if (head == null) return null; if (head.value == value) { return head.next; // 删除头节点 } ListNode current = head; while (current.next != null && current.next.value != value) { current = current.next; // 定位到目标节点的前驱节点 } if (current.next != null) { current.next = current.next.next; // 跳过目标节点 } return head; }

双向链表操作示例

双向链表的插入和删除需同时维护prev和next指针。

// 双向链表节点插入（在指定节点后插入） public void insertAfter(DoubleListNode node, int value) { DoubleListNode newNode = new DoubleListNode(value); newNode.next = node.next; newNode.prev = node; if (node.next != null) { node.next.prev = newNode; // 更新后继节点的prev指针 } node.next = newNode; } // 双向链表节点删除 public void deleteNode(DoubleListNode node) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } }

尾插法与头插法

尾插法将新节点插入到链表的末尾，保证链表元素的插入顺序与原始顺序一致，常用于按顺序构建链表。

操作逻辑：找到链表的尾节点（遍历至node.next == null的节点），将尾节点的next指向新节点。如果链表为空，头节点直接指向新节点。

代码示例（尾插法）：

public class LinkedListTailInsert { public ListNode tailInsert(ListNode head, int value) { ListNode newNode = new ListNode(value); if (head == null) { return newNode; } ListNode tail = head; while (tail.next != null) { tail = tail.next; } tail.next = newNode; return head; } public static void main(String[] args) { LinkedListTailInsert op = new LinkedListTailInsert(); ListNode head = null; head = op.tailInsert(head, 1); head = op.tailInsert(head, 2); head = op.tailInsert(head, 3); printList(head); // 输出：1 2 3 } public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); } }

头插法将新节点插入到链表的头部，新节点的next指向原头节点，同时更新头节点指向新节点，常用于实现链表倒序。

操作逻辑：创建新节点，新节点的next指向当前头节点，更新头节点为新节点。

代码示例（头插法）：

public class LinkedListHeadInsert { public ListNode headInsert(ListNode head, int value) { ListNode newNode = new ListNode(value); newNode.next = head; return newNode; } public static void main(String[] args) { LinkedListHeadInsert op = new LinkedListHeadInsert(); ListNode head = null; head = op.headInsert(head, 1); head = op.headInsert(head, 2); head = op.headInsert(head, 3); printList(head); // 输出：3 2 1 } public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); } }

任意位置插入

在链表的指定位置插入新节点，核心是先找到插入位置的前驱节点（Pre），再通过指针修改实现插入。

操作逻辑：定位插入位置的前驱节点pre，创建新节点，新节点的next指向pre.next，修改pre.next指向新节点。

边界情况：插入位置为0（头部）等同于头插法；插入位置为链表末尾等同于尾插法。

代码示例（在指定索引位置插入节点）：

public class LinkedListInsertAtIndex { public ListNode insertAtIndex(ListNode head, int index, int value) { ListNode newNode = new ListNode(value); if (index == 0) { newNode.next = head; return newNode; } ListNode pre = head; int currentIndex = 0; while (pre != null && currentIndex < index - 1) { pre = pre.next; currentIndex++; } if (pre == null) { ListNode tail = head; while (tail.next != null) { tail = tail.next; } tail.next = newNode; return head; } newNode.next = pre.next; pre.next = newNode; return head; } public static void main(String[] args) { LinkedListInsertAtIndex op = new LinkedListInsertAtIndex(); ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head = op.insertAtIndex(head, 1, 5); printList(head); // 输出：1 5 2 3 head = op.insertAtIndex(head, 5, 10); printList(head); // 输出：1 5 2 3 10 } public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); } }

遍历与打印

链表的遍历是通过游标（Cursor）从头节点开始，依次访问每个节点，直到节点为null。

代码示例（遍历与打印链表）：

public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); }

遍历与打印链表

链表的遍历是通过游标（Cursor）从头节点开始，依次访问每个节点，直到节点为null。遍历是所有链表操作的基础，打印链表则是遍历的直接应用，可通过循环拼接或重写toString方法实现。

代码示例（链表遍历与打印的多种方式）

public class LinkedListTraverse { // 方式1：普通循环遍历打印 public static void printListByLoop(ListNode head) { ListNode cur = head; if (cur == null) { System.out.println("链表为空"); return; } StringBuilder sb = new StringBuilder(); while (cur != null) { sb.append(cur.value); if (cur.next != null) { sb.append(" -> "); } cur = cur.next; } System.out.println("链表内容：" + sb.toString()); } // 方式2：递归遍历打印 public static void printListByRecursion(ListNode head) { if (head == null) { System.out.println(); return; } System.out.print(head.value); if (head.next != null) { System.out.print(" -> "); } printListByRecursion(head.next); } // 方式3：重写节点的toString，递归构建链表字符串 public static String listToString(ListNode head) { if (head == null) { return ""; } return head.toString() + (head.next != null ? " -> " + listToString(head.next) : ""); } public static void main(String[] args) { // 构建链表：1 -> 2 -> 3 -> 4 ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); printListByLoop(head); // 输出：链表内容：1 -> 2 -> 3 -> 4 printListByRecursion(head); // 输出：1 -> 2 -> 3 -> 4 System.out.println(listToString(head)); // 输出：1 -> 2 -> 3 -> 4 } }

遍历的核心意义

遍历是链表查找、统计、修改等操作的基础，无论是插入、删除，还是后续的快慢指针问题，都依赖对链表的熟练遍历，确保指针移动的准确性。

链表删除操作与面试高频考点（快慢指针）

链表的删除操作需要注意指针的处理，避免内存泄漏，而快慢指针是链表面试的核心考点，能解决一系列经典问题，包括寻找中间节点、判断环形链表、寻找倒数第K个节点等。

删除操作的分类处理

链表删除的核心是修改前驱节点的指针，跳过被删除的节点，需根据删除位置的不同进行分类处理，同时可借助虚拟头节点统一逻辑，简化代码。

指定位置删除

删除指定位置的节点，需分两种情况处理：删除头节点和删除非头节点（中间或末尾）。

• 删除头节点：直接将头节点更新为原头节点的下一个节点（head = head.next），原头节点失去引用，会被垃圾回收。
• 删除非头节点：需先找到被删除节点的前驱节点pre，修改pre.next指向被删除节点的下一个节点（pre.next = pre.next.next）。

代码示例（删除指定索引的节点，索引从0开始）

public class LinkedListDeleteAtIndex { // 删除链表中指定索引的节点，返回删除后的头节点 public ListNode deleteAtIndex(ListNode head, int index) { // 处理空链表 if (head == null) { return null; } // 删除头节点（索引为0） if (index == 0) { return head.next; // 头节点指向下一个节点 } // 寻找前驱节点pre（索引为index-1的节点） ListNode pre = head; int currentIndex = 0; while (pre != null && currentIndex < index - 1) { pre = pre.next; currentIndex++; } // 如果pre为null或pre.next为null，说明索引无效，直接返回原链表 if (pre == null || pre.next == null) { return head; } // 删除非头节点：pre.next指向pre.next.next pre.next = pre.next.next; return head; } public static void main(String[] args) { LinkedListDeleteAtIndex op = new LinkedListDeleteAtIndex(); // 构建链表：1 -> 2 -> 3 -> 4 ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); // 删除索引1的节点（值为2），预期链表：1 -> 3 -> 4 head = op.deleteAtIndex(head, 1); printList(head); // 输出：1 3 4 // 删除索引0的节点（头节点，值为1），预期链表：3 -> 4 head = op.deleteAtIndex(head, 0); printList(head); // 输出：3 4 // 删除索引2的节点（超出范围，无效操作），链表不变 head = op.deleteAtIndex(head, 2); printList(head); // 输出：3 4 } public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); } }

虚拟头节点（Dummy Node）技巧

删除操作中最麻烦的是需要特殊处理头节点的情况，虚拟头节点的核心作用是统一删除逻辑，避免对头节点进行特殊判断，让删除操作的处理逻辑完全一致，大大简化代码。

• 虚拟头节点的定义：创建一个不存储数据的新节点，其next指向原链表的头节点，新的虚拟头节点作为链表的"新入口"。
• 删除逻辑：无论删除哪个位置的节点，都统一找到被删除节点的前驱节点（此时前驱节点一定是虚拟头节点或后续节点），修改其next指针，最后返回虚拟头节点的next作为新头节点。

代码示例（使用虚拟头节点删除指定值的节点）：

public class LinkedListDeleteWithDummyNode { // 删除链表中所有值为target的节点，使用虚拟头节点统一逻辑 public ListNode deleteElement(ListNode head, int target) { // 创建虚拟头节点，next指向原头节点 ListNode dummy = new ListNode(-1); // -1为虚拟值，不存储实际数据 dummy.next = head; // 前驱节点pre初始为虚拟头节点 ListNode pre = dummy; // 遍历链表，找到需要删除的节点 while (pre.next != null) { if (pre.next.value == target) { // 删除pre.next指向的节点 pre.next = pre.next.next; } else { // 仅当不删除时，pre才后移 pre = pre.next; } } // 返回虚拟头节点的下一个节点，作为新头节点 return dummy.next; } public static void main(String[] args) { LinkedListDeleteWithDummyNode op = new LinkedListDeleteWithDummyNode(); // 构建链表：2 -> 1 -> 2 -> 3 -> 2 ListNode head = new ListNode(2); head.next = new ListNode(1); head.next.next = new ListNode(2); head.next.next.next = new ListNode(3); head.next.next.next.next = new ListNode(2); // 删除所有值为2的节点，预期链表：1 -> 3 ListNode newHead = op.deleteElement(head, 2); printList(newHead); // 输出：1 3 // 测试删除头节点的场景：链表：1 -> 2 -> 3，删除1，预期：2 -> 3 ListNode head2 = new ListNode(1); head2.next = new ListNode(2); head2.next.next = new ListNode(3); ListNode newHead2 = op.deleteElement(head2, 1); printList(newHead2); // 输出：2 3 } public static void printList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); } }

核心优势：

虚拟头节点让删除操作的逻辑完全统一，不需要判断是否删除头节点，代码更简洁，且降低了边界条件出错的概率，是面试中链表删除问题的常用技巧。

面试高频考点：快慢指针

快慢指针是链表面试的"杀手锏"，通过两个移动速度不同的指针，能在一次遍历中解决多个经典问题，包括寻找中间节点、判断环形链表、寻找倒数第K个节点等，是面试中的必考知识点。快慢指针的核心思想是：快指针移动速度是慢指针的两倍，通过两者的速度差来控制遍历节奏，解决特定问题。

寻找中间节点

利用快慢指针的速度差，当快指针遍历到链表末尾时，慢指针刚好指向链表的中间节点，适用于链表长度为奇数和偶数的情况。

核心逻辑：

初始化：快指针fast和慢指针slow均指向头节点。 移动规则：快指针每次移动2步（fast = fast.next.next），慢指针每次移动1步（slow = slow.next）。 终止条件：当快指针无法移动2步时（fast == null或fast.next == null），慢指针指向的节点即为中间节点。 奇偶处理：链表长度为奇数：中间节点唯一，慢指针指向正中间节点。链表长度为偶数：中间节点有两个，慢指针指向后一个中间节点（若需指向前一个，可调整移动逻辑）。

代码示例（寻找链表中间节点）：

public class FindMiddleNode { // 使用快慢指针寻找链表中间节点 public ListNode findMiddle(ListNode head) { if (head == null) { return null; } ListNode slow = head; ListNode fast = head; // 快指针每次走2步，慢指针每次走1步 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 当快指针无法再走2步时，慢指针即为中间节点 return slow; } public static void main(String[] args) { FindMiddleNode op = new FindMiddleNode(); // 测试1：奇数长度链表：1 -> 2 -> 3 -> 4 -> 5，中间节点为3 ListNode head1 = new ListNode(1); head1.next = new ListNode(2); head1.next.next = new ListNode(3); head1.next.next.next = new ListNode(4); head1.next.next.next.next = new ListNode(5); ListNode middle1 = op.findMiddle(head1); System.out.println("奇数长度链表中间节点：" + middle1.value); // 输出：3 // 测试2：偶数长度链表：1 -> 2 -> 3 -> 4，中间节点为3（后一个） ListNode head2 = new ListNode(1); head2.next = new ListNode(2); head2.next.next = new ListNode(3); head2.next.next.next = new ListNode(4); ListNode middle2 = op.findMiddle(head2); System.out.println("偶数长度链表中间节点：" + middle2.value); // 输出：3 } }

判断环形链表

环形链表是指链表的最后一个节点的next指向链表中的某个节点，形成环形。判断环形链表的核心是快慢指针是否相遇，如果相遇则说明有环，否则无环。

核心逻辑：

初始化：快指针fast和慢指针slow均指向头节点。 移动规则：快指针每次移动2步，慢指针每次移动1步（与寻找中间节点一致）。 终止条件：若快指针遇到null（fast == null或fast.next == null），说明链表无环，返回false。若快指针追上慢指针（fast == slow），说明链表有环，返回true。

为什么快慢指针一定能追上？

在有环的情况下，快指针比慢指针速度快，两者的距离每次缩小1步，最终会在环内相遇。

代码示例（判断链表是否有环）：

public class HasCycle { // 判断链表是否有环，有环返回true，无环返回false public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; // 空链表或只有一个节点，肯定无环 } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; // 快慢指针相遇，说明有环 if (fast == slow) { return true; } } // 快指针走到null，说明无环 return false; } public static void main(String[] args) { HasCycle op = new HasCycle(); // 测试1：无环链表：1 -> 2 -> 3 -> 4 ListNode head1 = new ListNode(1); head1.next = new ListNode(2); head1.next.next = new ListNode(3); head1.next.next.next = new ListNode(4); System.out.println("无环链表判断结果：" + op.hasCycle(head1)); // 输出：false // 测试2：有环链表：1 -> 2 -> 3 -> 4 -> 2（4指向2，形成环） ListNode head2 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); head2.next = node2; node2.next = node3; node3.next = node4; node4.next = node2; // 构造环 System.out.println("有环链表判断结果：" + op.hasCycle(head2)); // 输出：true } }

寻找倒数第K个节点

寻找链表倒数第K个节点，通过快慢指针可以高效解决，核心是让快指针先走K步，再让快慢指针同步前进，当快指针到达末尾时，慢指针指向的节点即为倒数第K个节点。

核心逻辑：

1. 初始化：快指针fast和慢指针slow均指向头节点。
2. 快指针先走K步：循环K次，让fast = fast.next，此时快慢指针的距离为K个节点。
3. 同步前进：如果快指针还能继续移动（fast != null），则快慢指针同时后移（fast = fast.next，slow = slow.next）。
4. 终止条件：当快指针到达null时，慢指针指向的节点即为倒数第K个节点。

边界处理：若K大于链表长度，返回null；若链表为空，返回null。

代码示例（寻找链表倒数第K个节点）：

public class FindKthFromEnd { // 寻找链表倒数第K个节点，返回该节点，不存在返回null public ListNode findKthFromEnd(ListNode head, int k) { if (head == null || k <= 0) { return null; } ListNode fast = head; ListNode slow = head; // 快指针先走k步 for (int i = 0; i < k; i++) { if (fast == null) { return null; // k大于链表长度，返回null } fast = fast.next; } // 快慢指针同步前进，直到快指针为null while (fast != null) { fast = fast.next; slow = slow.next; } // 此时slow指向倒数第k个节点 return slow; } public static void main(String[] args) { FindKthFromEnd op = new FindKthFromEnd(); // 构建链表：1 -> 2 -> 3 -> 4 -> 5 ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); head.next.next.next.next = new ListNode(5); // 寻找倒数第2个节点，预期为4 ListNode result1 = op.findKthFromEnd(head, 2); System.out.println("倒数第2个节点的值：" + result1.value); // 输出：4 // 寻找倒数第5个节点，预期为1 ListNode result2 = op.findKthFromEnd(head, 5); System.out.println("倒数第5个节点的值：" + result2.value); // 输出：1 // k=6大于链表长度，返回null ListNode result3 = op.findKthFromEnd(head, 6); System.out.println("k=6的结果：" + result3); // 输出：null } }

核心优势

该方法仅需一次遍历，时间复杂度O(n)，空间复杂度O(1)，是解决倒数第K个节点问题的最优解，也是面试中链表问题的高频考点。