LC19. Remove Nth Node From End of List



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.


    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 = ListNode(2) = head
        node_ptr = dummy_head

        #go forward to the node before the removed node
        for i in range(l_len - n):
            node_ptr =

        next_ptr = = 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

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) = head

        fast = dummy_head
        slow = dummy_head

        for i in range(n + 1):
            fast =

        while fast:
            fast =
            slow = =

Leave a Reply



    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](


Here is some inline `code`.

For more help see