LeetCode -- 19. Remove Nth Node From End of List

题意及思路

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

思路：@一开始的愚蠢方法，也没看到题目的注释。用的头插法反转单链表。。。很愚蠢的方法，详细见代码1。@得高人指点后，用的方法是双指针法。思路大致是：

代码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