描述

思路

快慢指针，快指针先走N步，走不够N步返回空。
慢指针和快指针一起走，当快指针到达终点，即快指针为null时，慢指针到达倒数第N个节点。
因为要删除倒数第N个，所以要记录之前的节点pre，假设倒数第N个节点为cur，删除操作即为：
pre.next = cur.next;
cur.next = null;

因为要返回删除后的头结点，所以假设一个虚拟头结点P，P.next = head;
初始时：pre = P，cur = pre.next;

最后返回P.next；

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode fast = head;while(n > 0 && fast != null) {fast = fast.next;n--;}if(n != 0){return null;}ListNode p = new ListNode();p.next = head;ListNode pre = p;ListNode cur = p.next;while(fast != null) {pre = pre.next;cur = cur.next;fast = fast.next;}pre.next = cur.next;cur.next = null;return p.next;}
}

面试公司

阿里