原创作品，可以转载，但是请标注出处地址：

LeetCode算法第19题（难度：中等）

题目：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。（English:Given a linked list, remove the n-th node from the end of list and return its head.）

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

提示：Maintain two pointers and update one with a delay of n steps.

简述实现思路：

　　普通思路：那就是两次遍历，首次遍历需要查出列表的长度，第二次遍历根据n找到指定删除的节点，删除即可。

　　进阶思路：根据提示中的内容，我们设立两个指针，分别指向相距n个节点的两个节点，然后保持n间距不变，遍历列表，当后面指针到达链表尾节点的时候，那么前面的指针正好指向的是待删除的节点。

Java代码实现：（简单实现）

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode removeNthFromEnd(ListNode head, int n) {11         ListNode node = head;12         int length = 0;13         do {14             length++;15             node = node.next;16         } while(node !=null);//结束时node指向尾节点17         18         if(n == length){
   //删除头结点19             return head.next;20         }else{21             node = head;22             int m = 0;23             while(true){24                 m++;25                 if(m == length - n){
   //找到待删元素的前一个元素26                     node.next = node.next.next;27                     break;28                 }29                 node = node.next;30             }31         }32         return head;33     }34 }

（进阶实现）

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode removeNthFromEnd(ListNode head, int n) {11         ListNode node = head;12         ListNode preNode = null;13         int m = 0;14         boolean isFirst = true;15         while(node != null){16             m++;17             if(m > n){18                 isFirst = false;19                 if(m == n + 1){20                     preNode = head;21                 }else{22                     preNode = preNode.next;23                 }24             }25             node = node.next;26         }27         if(isFirst){28             return head.next;29         }30         preNode.next = preNode.next.next;31         return head;32     }33 }

　　进阶思路解析：node节点可以看成是遍历条件，也可以看成是双指针的后指针，当这个指针移动到尾节点时，前指针就就位了，其实前指针指向的是待删节点的前节点，也就是说两个指针之间的距离其实是n+1。遍历开始后m递增，当m<=n的时候只移动后指针，当m>n时前指针开始移动。这样当遍历结束，前指针就位删除其后一个节点即可。注意头节点需要单独处理，处理逻辑为27-29行，当然也包括18行的逻辑。