Remove Nth Node From End of List

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

Have you met this question in a real interview?

Yes

Example

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

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

Note

The minimum number of nodes in list is n.

Challenge

O(n) time

/**

 * Definition for ListNode.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int val) {

 *         this.val = val;

 *         this.next = null;

 *     }

 * }

 */ 

public class Solution {

    /**

     * @param head: The first node of linked list.

     * @param n: An integer.

     * @return: The head of linked list.

     */

    ListNode removeNthFromEnd(ListNode head, int n) {

        // write your code here

        if(head == null || n <= 0) return head;

        ListNode node = head;

        for(int i = 0; i < n; i++){

            if(node == null) return null;

            node = node.next;

        }

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode preDelete = dummy;

        

        while(node != null){

            node = node.next;

            preDelete = preDelete.next;

        }

        preDelete.next = preDelete.next.next;

        return dummy.next;

    }

}