LinkedList - 19. Remove Nth Node From End of List

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

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.

Follow up:

Could you do this in one pass?

思路：

删除链表倒数第n个节点，就是要走到倒数第n+1个节点进行操作，如果一次遍历解决问题，就得使用两个指针，两个指针开始都在同一个位置，然后fast指针先走n+1步，然后slow指针开始和fast指针一起走，这样fast指针走到链表尾部的时候，slow指针刚好走到链表倒数n+1个节点位置。然后删除第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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        
        for (int i = 0; i < n + 1; i++) fast = fast.next;
        
        for(;fast != null;) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}