Remove nth node from the end of a Linked List
Detailed explanation and walkthrough for Problem 19 on LeetCode common interview question where we remove the nth node from the end of a LinkedList.
Table of contents
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 ๐คซ
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 ofn
iterations, i.e. after 2 iterations.
Here are the positions of the pointers on each iteration.
ptr1 = 1
andptr2 = 1
ptr1 = 2
andptr2 = 1
; we don't move the second pointer till we're on iterationi > n
.ptr1 = 3
andptr2 = 1
; we're on the 3rd iteration, we'll let the second pointer move on the next turn.ptr1 = 4
andptr2 = 2
ptr1 = 5
andptr2 = 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 behindptr1
byn
nodes. It'll only start moving whenptr1
has movedn
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
andptr2
, both set to thehead
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 byptr1
) is greater thann
. This indicates thatptr1
is nown
nodes ahead ofptr2
. 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 byptr2
.We create a new node with the value of the current node pointed to by
ptr2
and add it to ournewLL
. We move thecursor
to point to the newly added node.Moving the trailing pointer: We move the
ptr2
one node ahead only wheni > 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.
ptr2
is 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.