19. 删除链表的倒数第 N 个结点 (opens new window)

1.双指针法

一次遍历写法：使用双指针left和right维护一个长度为n的子链表，如果右指针没有到达尾指针即right.next不为空，那么同时移动左右指针。当right到达链表的最后一个节点，则当前left为倒数第N个节点。

找到left节点后需要删除该节点，因此需要设一个left的前驱指针pre，也同步和左右指针进行移动。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode phead=new ListNode(-1,head);
        ListNode pre=phead,left=head,right=head;
        while(right.next!=null){
            if(n>1){
                n--;
                right=right.next;
            }
            else{
                right=right.next;
                left=left.next;
                pre=pre.next;
            }
        }
        pre.next=pre.next.next;
        return phead.next; 
    }
}