题目要求

Given a linked list, remove the nth node from the end of list and return its head.For example,   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.Note:Given n will always be valid.Try to do this in one pass.

题意就是，从链表中移除倒数第n个节点（前提是这个被移除的节点一定存在）

思路一：利用数据结构ArrayList

从题目中可知，如果我们知道这个链表的大小，就可以直接删去节点。所以按照正常思路，我们可以先从根节点遍历一遍这个链表，得出链表的size后，再删去倒数第n个，也就是正数第size-n个节点。这样意味着遍历两次这个链表。虽然时间复杂度还是O(n),但是显然我们可以再一次遍历中完成这个任务。思路一就是将ArrayList和LinkedList相结合起来，通过ArrayList的下标完成要求

public class RemoveNthNodeFromEndofList_19 {    public ListNode removeNthFromEnd(ListNode head, int n) {        List
    
      nodeList = new ArrayList
     
      ();        ListNode start = new ListNode(0);        start.next = head;        nodeList.add(start);                while(head != null){            nodeList.add(head);            head = head.next;        }        int index = nodeList.size() - n;        nodeList.get(index-1).next = nodeList.get(index).next;                return nodeList.get(0).next;    }        public class ListNode {        int val;        ListNode next;        ListNode(int x) { val = x; }    }}
     
    

思路二：利用快慢指针

思路一直接利用了ArrayList的下标完成了任务。现在跳出下标的思路，从另一个角度分析。直接从题目要求入手，如果我们获得最后一个节点，那么到最后一个节点的距离为n的就是我们所要删去的节点。我们可以使用快慢节点。快慢节点之间的距离始终是n。当快节点到达终点时，此时的慢节点就是所要删去的节点。

public class RemoveNthNodeFromEndofList_19 {    public ListNode removeNthFromEnd2(ListNode head, int n) {        ListNode start = new ListNode(0);        start.next = head;        ListNode slow = start;        ListNode fast = start;                for(int i = 0 ; i