描述
思路
快慢指针,快指针先走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;}
}
面试公司
阿里