本题是删除链表的倒数第n个数，因为链表的性质，所以必须得遍历才知道链表有多长。 为了知道每个节点是倒数第几个节点，我们这里用回溯来计数，从而统计自己是第几个数。 另外我们删除第n个数的逻辑是，用第n+1个数去指向n-1个数（倒数）。 不过这存在一个特殊情况。n-1的数必然存在，它可以为空，但n+1的数可能不存在，当我们要删除的数就在链表的头部时，n+1这个元素为空，我们可以用一个节点指向空，但绝不能用空节点指向另外一个节点。 所以我们需要去判断第n个元素是否是头节点，如果是，那么我们就返回头结点的next即可。 代码的效果是100%和99.19%
这是我一个月前做的了，用的回溯思想，找到n-1和n+1的那个点。 其中也就一个特殊情况。
class Solution { private boolean flag = false;// 用以强制退出递归 ListNode nSubOne = null,nPlusOne = null,nn=null; public ListNode removeNthFromEnd(ListNode head, int n) { backtrack(head,n); //只需要考虑一个特殊情况：删除的是头元素，则无法用n+1->n-1来删除n，那么直接返回head的next即可 if(nn==head) return head.next; nPlusOne.next = nSubOne; return head; } public int backtrack(ListNode p, int n){ if(flag) return 0; //判断是否为空 if(p==null) return 0; int count = backtrack(p.next,n); count++; //进行判断，找到倒数n-1,n和n+1个数 if(count==n-1) nSubOne = p; else if(count==n+1){ nPlusOne = p; flag = true; } else if(count==n) nn = p; return count; } }一个多月后再做此题，回溯忘的一干二净，第一反应是多指针。 总共三个指针，一个preN，一个nextN，一个tail。 tail领先preN一共n次next（也就是中间隔了n-1个点），而nextN领先了preN两次next（也就是一个点）。 当三个指针同时往后跑，tail.next为空时便说明走到链表尾了。而此时preN刚好走到倒数第n个点的前面，nextN刚好走到倒数第n个点的后面。此时preN.net = nextN即可。 这里和上面一样，有特殊情况，当n=链表长度时，也就是tail先跑了之后next为空，则直接返回head.next即可。 看代码：
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //没有什么记忆了，感觉还是得多刷题，不然这种做过的题都没什么记忆，用什么方法还得想半天，其实很不应该 //需要考虑的是，这个是个链表，你只能一直访问下去 //需要找到第倒数第n个节点， //只用一趟就解决 //因为n有效，所以我直接把第一个节点往后走n个，领先n，然后两个一起往后走 //这样的话，当领先的为null时，那么就能找到第n个了 //这里因为是要删除，所以，还得搞一个近的 //所以是n-1是n+1，总共三个指针 if(n==0){ return head; } ListNode ans=head, preN=head, nextN=head, tail=head; //当链表长度等于n时，需要考虑，其他都不存在问题 for(int i=0; i<n; i++){ tail = tail.next; } if(tail==null){//n=链表长度 return head.next; } nextN = nextN.next.next; while(tail.next!=null){ tail=tail.next; preN = preN.next; nextN = nextN.next; } preN.next = nextN; return head; } }时间复杂度都是一样的，都是O(n)，没啥区别，空间复杂度也是O(1)，比上面的常数项略多。 只是一个不同的思路。
