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

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

**进阶:**你能尝试使用一趟扫描实现吗?

示例 1:

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

输入: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第26题——删除有序数组中的重复项