删除链表的倒数第N个节点

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

一、反转链表解法
Java代码：

/**
 * 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 rev = reverse(head);
        ListNode aftDel = delete(rev,n);
        return reverse(aftDel);
    }

    private ListNode delete(ListNode head,int n){
        if(head == null)
            return null;
        if(n == 1)
            return head.next;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            n--;
            if(n == 0){
                //删除当前节点
                pre.next = cur.next;
            }else{
                //往下找
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }

    private ListNode reverse(ListNode head){
        if(head != null){
            ListNode cur = head.next;
            ListNode pre = head;
            while(cur != null){
                ListNode n = cur.next;
                cur.next = pre;
                pre = cur;
                cur = n;
            }
            head.next = null;
            return pre;
        }
        return null;
    }
}

二、双指针解法

Java代码：

/**
 * 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 tmp = new ListNode(0);
        tmp.next = head;
        ListNode left = tmp;
        ListNode right = tmp;
        while(n != 0){
            right = right.next;
            n--;
        }
        while(right.next != null){
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return tmp.next;
    }
}