LeetCode每日一题： 删除链表的倒数第N个节点

先说一下我的思路：就是使用递归回溯的方法，先递归到最后一个节点，然后开始回溯，每回溯一次index加一，直到n == index - 1的时候，这个节点的下一个节点就是要删除的节点，直接赋为下个节点的下个节点即可，完成之后继续回溯到头节点，然后返回头节点即可。

  class Solution {
 int index = 1;
  int i = 1;
public ListNode removeNthFromEnd(ListNode head, int n) {
  if(head.next != null){
   i++;
   removeNthFromEnd(head.next,n);
  }
  if(n == index - 1){
    head.next = head.next.next;
  }    
  index++;
  //判断待删除节点是否为头节点
   if(n == i && index > i){
       return head.next;
   }else{
       return head;
   }
}
}

虽然时间复杂度挺好的，但是空间复杂度还是不太行

• 另一种解法：利用间隔为n的两个指针start，end，当end指针指向null时，start指针即为待删除节点的前一个指针，这样就只需要遍历一次就能完成删除操作（tql)

 class Solution {
 
public ListNode removeNthFromEnd(ListNode head, int n) {
 ListNode temp = new ListNode();
 temp.next = head;
 ListNode end = head;
 int index = 0;
  while(end != null){       
    end = end.next;
    if(index >= n+1){
        head = head.next;
    }
    index++;
  }
 if(index == n){
     return temp.next.next;
 }else{
     head.next = head.next.next;
 }
 return temp.next;
}
}

算是典型的空间换时间了把