Problem Statement in English

You’re given the head of a linked list, remove the n-th node from the end of the list and return its head.

There is a follow-up question: Could you do this in one pass?

Approach

If it wasn’t for the follow-up question, we could have solved this problem in two passes. In the first pass, we would traverse the linked list and store the nodes in a hashmap with their respective indices. In the second pass, we would find the node to be removed using the hashmap and update the next pointer of the previous node to skip the node to be removed.

In order to solve this problem in one pass, we will store the nodes in a hashmap with their respective indices while traversing the linked list.

Once we reach the end of the linked list, we will have the total number of nodes in the linked list. We can then calculate the index of the node to be removed from the start of the linked list using the formula: index_to_remove = total_nodes - n. We can then update the next pointer of the previous node to skip the node to be removed.

If the first node is the one to be removed, we will return the second node as the new head of the linked list. Otherwise, we will return the original head of the linked list.

And we’re done!

Solution in Python


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        hm = {}

        counter = 1

        temp = head

        while temp:
            hm[counter] = temp
            counter += 1
            temp = temp.next
        counter -= 1
        
        id = counter - n

        if id == 0: return head.next

        hm[id].next = hm.get(id + 2, None)
        return head

Complexity

  • Time: $O(n)$
    Since we are traversing the linked list once to store the nodes in a hashmap, the time complexity is O(n) where n is the number of nodes in the linked list.

  • Space: $O(n)$
    Since we are using a hashmap to store the nodes, the space complexity is O(n) where n is the number of nodes in the linked list.

And we are done.