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.

# Two pass

In the first pass, we will find out the length of the linked list. Then in the second pass, we will locate the len(linked_list) – n th element and remove it.

## Corner cases

### singleton linked list and n = 1

The new linked list should be empty

### Remove the head with n = len(linked list)

### Remove the end with n = 0

We can solve all these corner case by the use of dummy head.

### Code

```
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
Two pass
"""
l_len = 0
dummy_head = ListNode(1)
dummy_head = head
while dummy_head:
l_len += 1
dummy_head = dummy_head.next
dummy_head = ListNode(2)
dummy_head.next = head
node_ptr = dummy_head
#go forward to the node before the removed node
for i in range(l_len - n):
node_ptr = node_ptr.next
next_ptr = node_ptr.next.next
node_ptr.next = next_ptr
return dummy_head.next
```

We use the first loop to determine the length of the linked list. Then use a second for loop to find to pointer that points to the node that’s before the to-be-removed node. We use dummy head whose next pointer points to the head to make it simply

### use dummy head

An example:

D -> 1 -> 2 -> None

We set node_ptr, which points to the node before the to_be_removed node, to dummy head.

linked_list_len = 2

#### resolve corner cases of removing the head

if we want to remove the head, we need to remove the second node from the end. n = 2. In our code, the for loop will not execute, leaving the node_ptr = dummy_head. Without dummy head, we need to create a new node that serves as the node before head.

#### Simplify counting

We know the nth node from the end is also the linked_list_len – n – 1 th node.

If we use dummy head, the nth node from the end would also be linked_list_len – n th node.

# One pass

We will use two pointer to keep track both the current pointer iterating the linked list and also where the n + 1th element before the current pointer is. When the iteration finishes, the slow pointer will point to the n + 1 th element before the end, then we will remove the element next to the slower pointer and point the slower pointer’s next to the next of the removed node.

```
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
one pass
"""
dummy_head = ListNode(1)
dummy_head.next = head
fast = dummy_head
slow = dummy_head
for i in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next
```