学步园

【题目描述】Given a linked list, remove the nth node
from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

【算法思路】这道题的关键在于找倒数第n个结点的前驱结点：可以设置慢行指针slow和快行指针fast，让快行指针fast先走n步，然后同步地移动慢行指针slow和快行指针fast，这样它们之间的距离永远相差n个结点，当fast指针移动最后一个结点的时候，slow指向倒数第n个结点；

【编程步骤】

 * 1. 处理特殊情况：如果被移除的结点为头结点，则移除，并返回第二个结点作为头结点；
 * 2. 如果为其他情况，则找到倒数第n个结点的前驱结点 pre；

 * 3. 移除倒数第n个结点，即 pre.next=slow.next
或
pre.next=pre.next.next ;

【代码实现】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
		if(head==null)
			return null;
        ListNode fast=head;		
		int step=0;
		while(step<n&&fast!=null){
			step++;
			fast=fast.next;
		}
		// the removed node is the head
		if(fast==null){
			return head.next;
		}
		ListNode pre=head;
		ListNode slow=head;
		// find the positon of the removed node , the slow node
		while(fast!=null){
			pre=slow;
			slow=slow.next;
			fast=fast.next;			
		}
		// remove the node
		pre.next=slow.next;
		return head;
    }
}