Final Solution: Remove\(n^{th}\)Node from End of Linked List (LeetCode Problem 19)

A lot of y'all are really smart 🧠, and don't need a long-ass explanation of the code, so I like to give you the full code at the start and you can read on to understand my approach better if you like!

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        ptr1 = ptr2 = head
        newLL = ListNode()
        cursor = newLL

        i = 1
        while ptr1:
            if i > n:
                cursor.next = ListNode(ptr2.val, None)
                cursor = cursor.next
                ptr2 = ptr2.next
            ptr1 = ptr1.next
            i = i + 1

        if not ptr2.next: pass
        else: cursor.next = ptr2.next
        return newLL.next

Approach and Walkthrough

There are a couple of ways to solve this problem. Here, we'll tackle it using two pointers. This approach involves maintaining a lead pointer (ptr1) and a trailing pointer (ptr2). We'll strategically move these pointers to achieve our goal.

I have a confession to make, right off the bat. I cheated ... a little 😝! I came up with this solution only after reading the hint provided for this problem. And the hint goes:

Hint 🤫

Maintain two pointers and update one with a delay of n steps.

Genius! Let's visualise how that works using the example provided in the problem

Step 1: Understanding the pointers

This was the example provided to us. Parameter provided was n = 2, meaning, we need to delete the 2nd node from the last, i.e. 4.

Let's create two pointers. The first pointer will traverse the list normally. The second pointer will move after a lag ofniterations, i.e. after 2 iterations.

Here are the positions of the pointers on each iteration.

ptr1 = 1 and ptr2 = 1
ptr1 = 2 and ptr2 = 1 ; we don't move the second pointer till we're on iteration i > n .
ptr1 = 3 and ptr2 = 1 ; we're on the 3rd iteration, we'll let the second pointer move on the next turn.
ptr1 = 4 and ptr2 = 2
ptr1 = 5 and ptr2 = 3

We notice that we're exactly in front of the node which needs to be deleted. What remains is for us to attach current node (ptr2) to the next to next node. This is it! Let's do it! Here's a summary of what we did with the pointers.

Summary: How the pointers work

ptr1 (Lead pointer): This pointer will traverse the entire linked list. It'll move one step ahead each time.
ptr2 (Trailing pointer): This pointer will lag behind ptr1 by n nodes. It'll only start moving when ptr1 has moved n nodes ahead.

We've got the gist of the solution, we just need to iron out a few other kinks.

Step 2: Setting the Stage

We initialise two pointers, ptr1 and ptr2, both set to the head of the linked list.
We create a new empty linked list (newLL) to potentially hold the modified list and a pointer (cursor) to traverse this new list. We're basically just going to copy the original list into a new list while deleting the \(n^{th}\) node from the end.

Step 3: The Loop

We'll use a while loop to iterate through the original linked list using ptr1.

Iterator: We would need an iterator i to keep track of the total nodes traversed.
Condition to remove a node: Inside the loop, we check if i (a counter variable to keep track of the number of nodes traversed by ptr1) is greater than n. This indicates that ptr1 is now n nodes ahead of ptr2. This is the point where we want to remove the node.
Creating the new linked list: If you followed the demo closely, you'd have noticed that the ptr2 is the pointer in which we're actually deleting the node. ptr1 was just an Assistant (to the Regional Manager) to help us offset the nodes. Thus, our new LinkedList should actually be a copy of the path taken by ptr2.

We create a new node with the value of the current node pointed to by ptr2 and add it to our newLL. We move the cursor to point to the newly added node.
Moving the trailing pointer: We move the ptr2 one node ahead only when i > n
Termination of the loop: When ptr1 reaches the end of the list, ptr2 is at the \(n^{th}\) node from the end, the node to be deleted.

Step 4: Delete, but also cut corners

When ptr1 has reached the end of the node, one of two things could happen.

ptr2is also at the end: This is where n = 1, i.e. we need to remove the first node from the last. In this case, since we're already a step behind the node to be deleted, we simply return the linked list created so far.
There are more elements left in the list: Remember, ptr2 stops somewhere in the middle. We must delete the next element but also, keep the rest of the list intact. Solution? Just link the current node to node after the next!

Step 5: Final Touches

Returning the new head: Finally, we return the next pointer of the dummy node (newLL.next) because we started with an empty node and kept attaching the required nodes to this empty node. (Just print newLL at the end and you'll know what I mean).

And there we are! I'll append the full solution once hereon for you to go over the solution again!

Full solution: Once more

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        ptr1 = ptr2 = head
        newLL = ListNode()
        cursor = newLL

        i = 1
        while ptr1:
            if i > n:
                cursor.next = ListNode(ptr2.val, None)
                cursor = cursor.next
                ptr2 = ptr2.next
            ptr1 = ptr1.next
            i = i + 1

        if not ptr2.next: pass
        else: cursor.next = ptr2.next
        return newLL.next

Thanks for reading all the way to the end! Is there anything you don't understand? Please leave a comment and I will try my best to make it clearer for you.

Shreyan's blog