删除链表的倒数第n个节点

1.暴力解法
直接计算链表长度，再遍历到要删除的位置，时间复杂度：O（n），遍历结点，空间复杂度：O（1），辅助空间为常数级。
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
if(head==null)
return null;
ListNode t1=head;
ListNode t2=head;
int len=0;
while(t1!=null){//计算链表的长度
len++;
t1=t1.next;
}
if(len==n)//删除的结点为第一个
return head.next;
for(int i=0;i<len-n-1;i++){//t2移动到要删除的那个结点位置
t2=t2.next;
}
t2.next=t2.next.next;//删除结点
return head;
}
}
2.快慢指针解决
快指针先走n步，然后再两个一起走，当快指针走到末尾时，慢指针走到的位置就可以进行删除了。时间复杂度：O（n），遍历结点，空间复杂度：O（1），辅助空间为常数级。
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
if(head==null)
return null;
ListNode fast=head;
ListNode slow=head;
for(int i=0;i<n;i++){
fast=fast.next;
}
if(fast==null){//n刚好为链表的长度
return head.next;
}
while(fast.next!=null){//走到了要删除的位置，下一个结点即为要删除的
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;//删除结点
return head;
}
}