问题描述

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

类似的题有Leetcode876 链表的中间节点
剑指offer27 回文链表
大致思路就是快指针先移动n次 ，快慢指针再以相同的速度移动 ，当快指针为空时，慢指针的位置就是倒数第n个结点
这道题有一个坑就是头结点该如何删除，解决方法是构造一个头结点，将入参的头结点作为该结点的next结点
要删除倒数第n个节点，需要找到的是倒数第n+1个节点，因此fast指针需要先移动n+1次
image.png
假设要删除倒数第二个节点
快指针移动三次
image.png
fast和slow同步向后移动，直到fast指向null,需要移动两次
image.png
删除slow的下一个节点即可

代码

  1. class Solution {
  2.     public ListNode removeNthFromEnd(ListNode head, int n) {
  3.         ListNode start = new ListNode();
  4.         start.next = head;
  5.         ListNode fast = start;
  6.         ListNode slow = start;
  7.         for (int i = 0; i <=n; i ++) {
  8.             fast = fast.next;
  9.         }
  10.         while (fast != null) {
  11.             fast = fast.next;
  12.             slow = slow.next;
  13.         }
  14.         slow.next = slow.next.next;
  15.         return start.next;
  16.     }
  17. }

运行结果

image.png