Solving Leetcode 19. Remove Nth Node From End of List

“Remove Nth Node From End of List” is a popular problem on the online platform Leetcode, which tests a programmer’s ability to manipulate linked lists. The problem statement is as follows: Given a linked list, remove the nth node from the end of list and return its head.

A linked list is a data structure that consists of a series of nodes, where each node stores some type of value, which could pretty much be anything and a reference to the next node in the list. The first node in the list is called the head, and the last node in the list is called the tail. In this problem, we are given a linked list and a number n, and we are to remove the nth node from the end of the list and return its head.

Approaching the problem

One approach to solving this problem is to use the two pointer method. This is where one pointer moves ahead by a certain amount of steps and the other pointer starts from the head of the list. When the first pointer reaches the end of the list, the second pointer would be pointing at the node that precedes the nth node from the end. To remove the nth node, we simply update the next reference of the second pointer to skip over the nth node.

Here is the code for this approach in Python:

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        
        for i in range(n):
            first = first.next
        
        while first.next:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        
        return dummy.next
</code>

In this solution, we first create a dummy node with a value of 0 and next reference pointing to the head of the original linked list. This is done to handle the edge case where the head of the list needs to be removed. We then initialize two pointers, first and second, both pointing to the dummy node.

The first pointer is then moved ahead by n steps, after which both pointers are moved ahead one step at a time until the first pointer reaches the end of the list. At this point, the second pointer would be pointing at the node that precedes the nth node from the end.

Finally, we update the next reference of the second pointer to skip over the nth node, effectively removing it from the list. The head of the modified linked list is then returned.

Time and space Complexity

Time Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the linked list twice, once to move the first pointer n steps ahead, and once to move both pointers until the first pointer reaches the end of the list. The time taken to traverse the linked list is proportional to the number of nodes in the list, so the time complexity is O(n).

Space Complexity

The space complexity of the solution is O(1), because we only use a constant amount of extra space to store the two pointers and the dummy node. We do not use any additional data structures that grow with the size of the linked list, so the space complexity remains constant at O(1).

In general, a time complexity of O(n) is considered efficient for linked list problems, and a space complexity of O(1) is considered optimal. The solution presented in this article meets these criteria, making it a highly efficient solution for the “Remove Nth Node From End of List” problem.

The “Remove Nth Node From End of List” problem is a great way to test a programmer’s understanding of linked lists and their manipulation. The solution presented in this article uses a two-pointer approach and has a time and space complexity of O(n) and O(1) respectively, making it a highly efficient solution.

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.