[路飞]_leetcode-19-删除链表的倒数第 N 个结点-阿里云开发者社区

[路飞]_leetcode-19-删除链表的倒数第 N 个结点

2022-04-25 79

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： leetcode-19-删除链表的倒数第 N 个结点

网络异常，图片无法展示

「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

示例 1：

网络异常，图片无法展示

输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]
复制代码

示例 2：

输入： head = [1], n = 1
输出： []
复制代码

示例 3：

输入： head = [1,2], n = 1
输出： [1]
复制代码

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

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

本题并不难，只是在查找倒数第 n 个节点的基础上加了一个删除操作解题思路如下：

根据题意可得，如果链表只有一个节点，那么此时 n 必然等于 1,那么删除倒数第一个节点之后的链表为空，所以特判如果链表只有一个节点，直接返回 null 即可
创建虚拟头节点，因为本题删除的节点有可能是头节点，所以创建虚拟头节点可以方便我们的操作，简化处理逻辑
定义三个指针 pre 指向虚拟头，target、next 指向 head
将 next 指针向后走 n 步
pre、target、next 一起向后走，直到 next 指向 null,此时 target 指向倒数第 n 个节点
将 pre 指针指向元素（也就是 target 前一个元素）的 next 指针指向 target.next 来达到从链表中删除 target 节点的目的
返回虚拟头节点的下一个节点即可

整体过程如下：

网络异常，图片无法展示

代码如下：

var removeNthFromEnd = function(head, n) {
  // 特判 如果链表只有一个节点，则 n 必然为1，此时删除倒数第一个节点后链表为空
  if(head.next === null) return null;
  // 创建虚拟头节点
  const vhead = new ListNode(0);
  vhead.next = head;
  // 定义三个指针
  let pre = vhead,
  target = head,
  next = head;
  // next向后走n步
  while(n){
    n--;
    next = next.next;
  }
  // 当next不为空的时候，三个指针一起向后走
  while(next){
    pre = pre.next;
    target = target.next;
    next = next.next;
  }
  // 此时target指向的就是倒数第n个节点
  // 通过将pre.next指向target.next的方法从链表中删除target
  pre.next = target.next;
  return vhead.next;
};
复制代码