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