019. 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.

节点定义：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

思路一：使用两个指针，第一个指针先走n步，后面两个指针同时走，当第一个指针走到最后的时候，第二指针指的就是所要找的节点。但是leetcode上面的链表头结点是带存储值的。这个边界和存储情况不太一样。
思路二：效率比较低下，走两遍，先求出链表的长度length，这样找倒数第n个元素就比较好操作了。
coding:

/**
 * @author scavenger
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        //用两个指针 第一个走
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
            if (first == null) {
                return second.next;
            }
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        //删除最后一个节点的情况：
        if (n == 1) {
            second.next = null;
        } else {
            //不是最后一个节点
            second.next = second.next.next;
        }

        return head;
    }
}