# LC19. 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.

# 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 end with n = 0

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

### Code

``````    def removeNthFromEnd(self, head, n):
"""
:type n: int
:rtype: ListNode
Two pass
"""
l_len = 0
l_len += 1

#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

``````

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

An example:
D -> 1 -> 2 -> None
We set node_ptr, which points to the node before the to_be_removed node, to dummy head.

#### 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 n: int
:rtype: ListNode
one pass
"""