高效删除链表倒数节点最优实现

简介: 要删除链表的倒数第 n 个节点,并返回链表的头节点,我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针:快指针和慢指针。

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

提示:

链表中结点的数目为 sz

  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

你能尝试使用一趟扫描实现吗?

具体实现

要删除链表的倒数第 n 个节点,并返回链表的头节点,我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针:快指针和慢指针。快指针先向前移动 n 步,然后慢指针从链表的头节点开始,与快指针同时移动。当快指针到达链表的末尾时,慢指针所在的下一个节点就是倒数第 n 个节点。

以下是使用 Java 实现的删除链表倒数第 n 个节点的函数:

class ListNode {
   int val;
   ListNode next;
   ListNode(int x) { val = x; }
}

public class Solution {
   public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(0); // 创建一个哑节点,它的下一个节点是头节点
       dummy.next = head;
       ListNode fast = dummy;
       ListNode slow = dummy;

       // 快指针先走 n 步
       for (int i = 0; i < n; i++) {
           fast = fast.next;
       }

       // 快慢指针同时移动,直到快指针指向链表的末尾
       while (fast.next != null) {
           fast = fast.next;
           slow = slow.next;
       }

       // 慢指针的下一个节点就是倒数第 n 个节点,删除它
       slow.next = slow.next.next;

       return dummy.next; // 返回哑节点的下一个节点,即新的头节点
   }
}

使用示例:

public class Main {
   public static void main(String[] args) {
       // 示例 1
       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);
       int n1 = 2;
       ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
       printList(newHead1); // 应该输出 [1,2,3,5]

       // 示例 2
       ListNode head2 = new ListNode(1);
       int n2 = 1;
       ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
       printList(newHead2); // 应该输出 []

       // 示例 3
       ListNode head3 = new ListNode(1);
       head3.next = new ListNode(2);
       int n3 = 1;
       ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
       printList(newHead3); // 应该输出 [1]
   }

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

代码输出结果与题目中的示例输出是一致, V 哥的这个实现中,使用了一个哑节点来简化边界条件的处理,这样即使要删除的是头节点,代码也能正常工作。这个方法只需要一趟扫描,因此时间复杂度是 O(sz),其中 sz 是链表的长度。

实现过程和步骤如下

下面 V 哥把实现过程再详细说明一下,为了帮助你更好的理解代码的逻辑实现:

  1. 创建一个哑节点(dummy node),并将其设置为链表的头节点之前的一个节点。哑节点的引入是为了简化边界条件的处理,特别是当需要删除的节点是头节点时。
  2. 初始化两个指针:快指针(fast)和慢指针(slow),它们都指向哑节点。
  3. 快指针先向前移动 n 步。这样,快指针和慢指针之间就保持了 n 个节点的距离。
  4. 快指针和慢指针同时向前移动,直到快指针到达链表的末尾(即快指针的下一个节点为 null)。此时,慢指针的位置就是倒数第 n 个节点的前一个节点。
  5. 修改慢指针的 next 指针,使其指向下一个节点的下一个节点,从而跳过倒数第 n 个节点,实现删除操作。
  6. 返回哑节点的下一个节点,即新的头节点。

这个方法的核心思想是利用快慢指针的差距来找到倒数第 n 个节点。快指针先走 n 步,然后快慢指针一起移动,直到快指针到达链表末尾。此时,慢指针所在的位置就是倒数第 n 个节点的前一个节点,这样就可以很容易地删除倒数第 n 个节点。

小结

V哥经过测试,坐实了这个方法只需要一趟扫描,所以时间复杂度是 O(sz),其中 sz 是链表的长度。空间复杂度是 O(1),因为只需要常数级别的额外空间来存储快慢指针和哑节点。

相关文章
|
2月前
|
存储 Python
链表中插入节点
链表中插入节点
|
1月前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
2月前
|
存储 Python
删除链表节点详解
删除链表节点详解
|
22天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
2月前
|
存储 Python
链表中删除节点
链表中删除节点
|
2月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
39 6
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
30 1
|
1月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
2月前
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
24 1
|
1月前
|
存储
删除链表的节点
删除链表的节点
15 0