链表-LeetCode19：Remove Nth Node From End of List

一、问题描述：
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

二、解决思路
方法一：先遍历链表，计算出链表长度lens，接着继续从表头遍历链表，找到第（lens - n）个节点，并将其节点的下一个节点指向下下个节点
时空复杂度：2O(n)、O(1)
方法二：采用双指针方法，一前一后从表头遍历链表，两指针相距n个节点

三 算法实现
这里只给出方法二算法实现，如下所示

public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 搞一个哨兵节点
      if(n == 0) return head;
      if(head == null) return null;
      ListNode tp = new ListNode();
      tp.next = head;
      ListNode tital = tp;
      ListNode pre = tp;
      int num = 0;
      while(head != null){
          head = head.next;
          num++;
          if(num > n){
              pre = pre.next;
          }
      }
      if(pre.next != null){
          pre.next = pre.next.next;
      } else{
          pre.next = null;
      }
      return tital.next;
}