题意及思路

题意：略（注：题意问你能否只一遍遍历，找到要删除的节点？）

思路：@一开始的愚蠢方法，也没看到题目的注释。用的头插法反转单链表。。。很愚蠢的方法，详细见代码1。@得高人指点后，用的方法是双指针法。思路大致是：维护两个指针，先让first向后移动n个 位置，然后让first 和 second 同时向后移（直到second到达尾节点），当first到达尾节点时，second到达倒数第n+1个节点，此时可以执行删除操作。second.next = second.next.next。

附图


代码1 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode top = new ListNode(Integer.MIN_VALUE);
        top.next = head;
        ListNode p = top;
        if(n==1){
            while(p.next.next!=null) p = p.next;
            p.next = null;
            return top.next;
        }
        top = reverseList(head);
        p = top.next;
        int id = 0;
        while(p!=null){
            if(++id==n-1){
                if(p.next!=null) p.next = p.next.next;
                else p.next = null;
            }
            p = p.next;
        }
        return reverseList(top.next).next;
    }
    
    private ListNode reverseList(ListNode head){
        ListNode top = new ListNode(Integer.MIN_VALUE);
        top.next = null;
        ListNode t,p=head;
        while((t=p)!=null){
            p = p.next;
            t.next = top.next;
            top.next = t;
        }
        return top;
    }
}


代码2 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode top = new ListNode(-1);
        top.next = head;
        ListNode first = top,second = top;
        while(n-->0) first = first.next;
        while(first.next!=null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return top.next;
    }
}