题目地址(19. 删除链表的倒数第 N 个结点)

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目描述

  1. 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
  3. 进阶：你能尝试使用一趟扫描实现吗？
  7. 示例 1：
  9. 输入：head = [1,2,3,4,5], n = 2
  10. 输出：[1,2,3,5]
  13. 示例 2：
  15. 输入：head = [1], n = 1
  16. 输出：[]
  19. 示例 3：
  21. 输入：head = [1,2], n = 1
  22. 输出：[1]
  27. 提示：
  29. 链表中结点的数目为 sz
  30. 1 <= sz <= 30
  31. 0 <= Node.val <= 100
  32. 1 <= n <= sz

前置知识


公司

  • 暂无

思路

image.png

关键点

  • 定义快慢指针
  • 虚拟头结点

代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for singly-linked list.
  4.  * public class ListNode {
  5.  *     int val;
  6.  *     ListNode next;
  7.  *     ListNode() {}
  8.  *     ListNode(int val) { this.val = val; }
  9.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  10.  * }
  11.  */
  12. class Solution {
  13.         public ListNode removeNthFromEnd(ListNode head, int n) {
  14.             //定义一个虚拟头结点
  15.             ListNode touNode = new ListNode(-1, head);
  16.             //定义快慢指针 都指向头结点
  17.             ListNode fast = touNode;
  18.             ListNode slow = touNode;
  19.             //让快指针执行n次
  20.             while (n-- > 0) {
  21.                 fast = fast.next;
  22.             }
  23.             //当快指针.next不等于空时 快慢指针++ 加到最后时 快指针在队伍的最后端 慢指针在待删除的节点的前方
  24.             while (fast.next != null) {
  25.                 fast = fast.next;
  26.                 slow = slow.next;
  27.             }
  28.             //使慢指针的下个节点 指向下个节点的下个节点
  29.             slow.next = slow.next.next;
  30.             return touNode.next;
  31.         }
  32.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：19. 删除链表的倒数第 N 个结点(2) - 图2#card=math&code=O%28n%29&id=lF0ht)
  • 空间复杂度：19. 删除链表的倒数第 N 个结点(2) - 图3#card=math&code=O%28n%29&id=hKsEe)