题目链接

19. 删除链表的倒数第 N 个结点

题目描述

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

示例 1：
image.png

  1. 输入：head = [1,2,3,4,5], n = 2
  2. 输出：[1,2,3,5]

进阶：你能尝试使用一趟扫描实现吗？

解题思路

1. 双指针

利用快慢指针，fast 先前进 n 步，然后 slow 和 fast 一起前进；当 fast.next = null 时，slow 指针停留在倒数第 n 个节点的前一个节点。

使用哨兵节点 dummy 来解决当链表中只有一个节点，并且 n 为 1，也就需要删除的节点是头节点的情况。

注意：

  • 题目保证了 n 的有效性，即 n 在链表长度范围内。如果题目未保证 n 的有效性，需要特殊判断。见代码中注释。

    1. class Solution {
    2.   public ListNode removeNthFromEnd(ListNode head, int n) {
    3.       ListNode dummy = new ListNode(-1);
    4.       dummy.next = head;
    5.       ListNode fast = dummy;
    6.       ListNode slow = dummy;
    7.       while (n != 0) {
    8.           fast = fast.next;
    9.           n--;
    10.       }
    11.       // 如果 n 未保证有效性则添加注释代码
    12.       /*
    13.           if (fast == null) {
    14.               return head;
    15.           }
    16.       */
    17.       while (fast.next != null) {
    18.           fast = fast.next;
    19.           slow = slow.next;
    20.       }
    21.       slow.next = slow.next.next;
    22.       return dummy.next;
    23.   }
    24. }

  • 时间复杂度：LeetCode19. 删除链表的倒数第 N 个节点 - 图2

  • 空间复杂度：LeetCode19. 删除链表的倒数第 N 个节点 - 图3