一、题目
二、题解
2.1 双指针
由于我们需要找到倒数第 n 个节点，因此可以使用两个指针fast 和 slow 同时对链表进行遍历，并且 fast 比 slow 超前 n 个节点。当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。
具体地，初始时 fast 和 slow 均指向头节点。首先使用 fast 对链表进行遍历，遍历的次数为 n。此时，fast 和 slow 之间间隔了 n-1 个节点，即 fast 比 slow 超前了 n 个节点。
在这之后，同时使用 fast 和 slow 对链表进行遍历。当 fast 遍历到链表的末尾（即 fast 为空指针）时，slow 恰好指向倒数第 n 个节点。
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
if(head == null)
return null;
ListNode fast = head;
// 慢指针用于标记被删除点
ListNode slow = head;
// 被删除点的前一个节点
ListNode pre = new ListNode(-1);
// 指向头结点
pre.next = head;
// 利用快慢指针找到被删除点的位置
for(int i = 0;i<n;i++){
fast = fast.next;
}
while(fast!= null){
fast = fast.next;
slow = slow.next;
pre = pre.next;
}
// slow == head表示被删除点为头节点，删除头节点后，新的头节点为原头结点的下一节点
if(slow == head) return head.next;
// 被删除点不是头结点，则将被删除点的前一节点指向被删除点的下一节点，完成指定节点的删除
pre.next = slow.next;
return head;
}
}2.2 计算链表长度
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
int length = 0;
ListNode p = head;
ListNode q = head;
// 获取链表的长度
while(head != null){
length++;
head = head.next;
}
if(length < 2){
return null;
}
// 特殊情况
if(n == length){
return q.next;
}
int i = 0;
while(p != null){
i++;
if(i == length - n){
// 删除结点
p.next = p.next.next;
}
p = p.next;
}
return q;
}
}