当前位置：首页 > news >正文

Java 代码详解：删除链表中的倒数第 N 个节点

news 来源：原创 2024/9/19 13:29:40

Java 代码详解：删除链表中的倒数第 N 个节点（含双指针优化）

在编程中，链表的操作是一个非常常见且重要的课题。本文将带你逐步实现和优化删除单链表中倒数第 N 个节点的功能，并通过双指针技巧优化代码，使其更加高效。

题目描述

给定一个链表，删除链表的倒数第 N 个节点，并返回链表的头节点。例如，对于链表 1 -> 2 -> 3 -> 4 -> 5，如果要删除倒数第 2 个节点，删除后的链表为 1 -> 2 -> 3 -> 5。

基础实现代码

以下是基础的实现方式：

public ListNode removeNthFromEnd(ListNode head, int n) {// 计算链表长度int length = 0;ListNode cur = head;while (cur != null) {length++;cur = cur.next;}// 计算需要删除节点的前一个节点的索引int index = length - n;// 创建一个虚拟头节点ListNode dummy = new ListNode(0);dummy.next = head;// 将指针移动到需要删除节点的前一个节点cur = dummy;for (int i = 0; i < index; i++) {cur = cur.next;}// 删除节点cur.next = cur.next.next;// 返回处理后的链表头节点return dummy.next;
}

基础实现分析

计算链表长度：首先遍历链表一次来计算它的长度。
计算删除节点的前一个节点的位置：使用链表总长度和需要删除的倒数第 N 个节点的位置来计算出删除节点的前一个节点的索引。
删除节点：找到要删除节点的前一个节点后，修改指针，使其直接跳过要删除的节点。

优化：使用双指针技巧

虽然上述代码功能正常，但我们可以通过双指针优化，使代码更加高效。双指针可以在一次遍历中完成删除节点的操作，从而降低时间复杂度。

双指针优化后的代码

public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟头节点ListNode dummy = new ListNode(0);dummy.next = head;// 初始化两个指针，first 和 second 都指向虚拟头节点ListNode first = dummy;ListNode second = dummy;// 将 first 指针向前移动 n+1 步，使得 first 和 second 之间间隔 n 个节点for (int i = 0; i <= n; i++) {first = first.next;}// 同时移动 first 和 second 指针，直到 first 指向 nullwhile (first != null) {first = first.next;second = second.next;}// 此时 second 指向的节点是要删除节点的前一个节点second.next = second.next.next;// 返回处理后的链表头节点return dummy.next;
}

双指针优化分析

双指针初始化：first 和 second 两个指针都初始化为指向虚拟头节点 dummy。这是为了处理边界情况，如链表长度小于 N 的情况。
移动 first 指针：将 first 指针向前移动 n + 1 步。这样 first 和 second 之间的间隔就是 N 个节点。
同时移动两个指针：然后同时移动 first 和 second 指针，直到 first 指针到达链表的末尾。此时，second 指针正好指向要删除的节点的前一个节点。
删除节点：完成删除操作只需将 second.next 指向 second.next.next。
返回链表：返回删除节点后的链表头节点，即 dummy.next。