leetcode刷题-[19]删除链表的倒数第 N 个结点

本文主要是介绍leetcode刷题-[19]删除链表的倒数第 N 个结点，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你一个链表，删除链表的倒数第 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]

思路1

• 删除链表的倒数第 n 个结点，可以联想到 倒数第n个节点和链表结束的null节点是一个 “窗口”，知道这一点我们维护这个窗口就好了
• 因为涉及到了 修改链表，所以我们一般会设置一个 dumb node
• 维护快慢指针 slow fast
• 首先移动 fast n + 1 次 （为什么是n + 1 ，自己画图就明白了）
• 同时移动slow 和 fast，直到fast == null，此时slow节点即为要删除的节点的前置节点
• 常规删除就可以了

关键代码

public ListNode removeNthFromEnd(ListNode head, int n) {
  // [d,1,2,3,4,5,null]
  if (head == null || n <= 0) return head;
  ListNode d = new ListNode(-1);
  d.next = head;
  ListNode slow = d;
  ListNode fast = d;

  while (n-- >= 0) { // n + 1
    fast = fast.next;
  }

  while (fast != null) {
    slow = slow.next;
    fast = fast.next;
  }

  slow.next = slow.next.next;
  return d.next;
}

思路2

• 还有一种做法是维护一个指针先遍历一遍链表，求出总长度len
• 然后根据n计算出被删除结点的前置节点s的位置
• 重置指针p，遍历到前置节点s的位置
• 常规删除

该方法遍历了链表2次，极端情况如果链表过长，n过大，代价挺大，不推荐

关键代码

public ListNode removeNthFromEnd(ListNode head, int n) {
  // [d,1,2,3,4,5,null]
  if (head == null || n <= 0) return head;
  ListNode d = new ListNode(-1);
  d.next = head;
  ListNode p = d;
  int len = 0;
  while (p != null) {
    len++;
    p = p.next;
  }
  p = d;
  int dis = len - n - 1;
  for (int i = 0; i < dis; i++) {
    p = p.next;
  }

  p.next = p.next.next;
  return d.next;
}

这篇关于leetcode刷题-[19]删除链表的倒数第 N 个结点的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！