## Description

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. After removing the second node from the end, the linked list becomesn= 21->2->3->5.

**Note:**

Given *n* will always be valid.

**Follow up:**

Could you do this in one pass?

## Explanation

We introduce a preDelete pointer first and place it at the beginning of the linked list.

- Move head pointer first so that the distance between preDelete and head pointer would be N nodes.
- Move head and preDelete pointer together until head is reaching to the end.
- Modify preDelete pointing node.next to the next node of the delete node.

## Java Solution

/** * 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) { if (n <= 0) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode preDelete = dummy; for (int i = 0; i < n; i++) { if (head == null) { return null; } head = head.next; } while (head != null) { preDelete = preDelete.next; head = head.next; } preDelete.next = preDelete.next.next; return dummy.next; } }

## Python Solution

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
slow = head
fast = head
for i in range(0, n):
fast = fast.next
if fast == None:
head = head.next
return head
while fast.next != None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
```

- Time complexity: O(L). The algorithm makes one traversal of the list of L nodes.
- Space complexity: O(1). We only used constant extra space.

Please always provide Time Complexity and Space Complexity.

Hi Gaurav,

I think there’s a small mistake in java solution, while loop should be head.next!=null vs head!=null. Please correct me If I am wrong.