给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 
示例：
 
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
 
说明：
 
给定的 n 保证是有效的。
 
采取暴力法：
 
/**
  * 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) {
         if(head==null) return head;
         ListNode dum = new ListNode(0);
         ListNode cur = dum;
         int len=0;
         cur.next=head;
         while(head!=null)
         {
           head=head.next;
           len++;
         }
         for(int i=1;i<=len-n;i++)    //记得循环次数问题  初始cur在head前一位
                 cur=cur.next;
         cur.next=cur.next.next;   //切记不能写成cur=cur.next.next   只是移动  并没有指向
         return dum.next;
     }
 }
 

19. 删除链表的倒数第N个节点
 
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 
示例：
 
给定一个链表: 1->2->3->4->5, 和 n = 2.
 
当删除了倒数第二个节点后，链表变为 1->2->3->5.
 说明：
 
给定的 n 保证是有效的。
 
进阶：
 
你能尝试使用一趟扫描实现吗？
 
来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
PS:
 递归大法：1ms
 
/**
 * 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) {
       return removeNode(head,n)==n?head.next:head;
	}	
	public int removeNode(ListNode node,int n) {		
		if(node.next == null)  return 1;
		int m = removeNode(node.next, n);
		if(m == n) 
			if(m == 1) node.next = null;
			else node.next = node.next.next;
		return m+1;
	}
}

19.删除链表倒数第N个节点Java
 
题目描述
 
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 
进阶：你能尝试使用一趟扫描实现吗？
 
输入输出样式
 
示例1：
 输入：head = [1,2,3,4,5], n = 2
 输出：[1,2,3,5]
 
 
示例2：
 输入：head = [1], n = 1
 输出：[]
 
 
 
本题来自LeetCode：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 
 
思路
 
常规方法：遍历两边，第一遍求总节点数，第二遍找到倒数第N个节点
我的思路：构建一个长度为N的“卡尺”和卡尺前的prev节点(用于删除元素)，移动卡尺和prev知道卡尺的右端right.next为空说明到达尾端，这样卡尺的左端left就是倒数第N个元素了，直接pre.next = left.next即可。这样只需要遍历一遍链表。
 
算法分析
 
时间复杂度O(n），空间复杂度为O(1)
 
求解函数
 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution19 {
    public static void main(String[] args) {
        ListNode n5 = new ListNode(5, null);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);
        ListNode cur = n1;
        Solution19 sol = new Solution19();
        cur = sol.removeNthFromEnd(n1, 2);
        while (cur != null) {
            System.out.println(cur);
            cur = cur.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        ListNode dum = new ListNode(0, head);
        ListNode left = head, right = head, prev = dum;
        //建立卡尺
        for (int i = 1; i < n; ++i) {
            right = right.next;
        }
        //直到卡尺到达尾部
        while (right.next != null) {
            right = right.next;
            prev = prev.next;
            left = left.next;
        }
        //删除第N个节点
        prev.next = left.next;
        return dum.next;
    }
}
 
测试结果
 

Java实现Leetcode链表-删除链表的倒数第N个节点
 
一、 问题描述
 
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 
示例：
 
给定一个链表: 1->2->3->4->5, 和 n = 2.
 
当删除了倒数第二个节点后，链表变为 1->2->3->5.
 说明：
 
给定的 n 保证是有效的。
 
进阶：
 
你能尝试使用一趟扫描实现吗？
 
方法一：两次扫描
 
第一次扫描求出链表长度；
 第二次将倒数n个转化成正数length-n个，然后执行删除。
 
实现代码如下：
 
public static ListNode removeNthFromEnd(ListNode head, int n) {
    	  ListNode dummy= new ListNode(0);
    	  dummy.next=head;
    	  int length=0;
    	  ListNode first=head;
    	  while(first!=null) {
    		  length++;
    		  first=first.next;
    	  }
    	  length-=n;
    	  first=dummy;
    	  while(length>0) {
    		  length--;
    		  first=first.next;
    	  }
    	  first.next=first.next.next;
          return dummy.next;
          }
 
方法二
 
一次扫描
 
实现代码如下：
 
 public static ListNode removeNthFromEnd(ListNode head, int n) {
    	  //定义一个哑结点指向头结点
    	  ListNode dummuy=new ListNode(0);
    	  dummuy.next=head;
    	  ListNode p1=dummuy,p2=dummuy;//定义两个工作指针
    	  //先让p1移动n次
    	  while(n>0) {
    		  n--;
    		  p1=p1.next;
    	  }
    	  //让p1和p2一起移动，至到p1.next=null
    	  while(p1.next!=null) {
    		  p1=p1.next;
    		  p2=p2.next;
    	  }
    	  //执行删除
    	  p2.next=p2.next.next;
    	  return dummuy.next;
      }