“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.