Remove Nth node from End of the List

Given the head of a linked list, remove the nth node from the end of the list and return its head.
So the given linked list is and n = 2, need to remove 2nd node from the end of the Linked List.

From the end of the list [4] is the desired Nth Node. After removing the nth node, the final Linked List will look like this.

Intuition

If you already solved Delete the Middle node of a Linked List, You already know that to remove a node from Linked List, we must need it's the previous/left node and next/right node to do something like this

Here is Left Node [3] is breaking link with the desired Nth Node [4] and establishing connection with it's next node [5].
🤔 But how can we determine that we have reached at the node before Nth Node?
Well we need another pointer Right and move both Left and Right pointer in such a way that by the time Right pointer reaches at NULL the Left pointer reaches at the Node before Nth Node. Let's visualize it first.

So basically, there must be N Number of Nodes in between Left and Right pointer.

Pointer Placement

First Place the Right at the Head and move it N Nodes Forward.

Now run N iterations from the Head to move Right pointer forward.

Let's write a Helper Function for this

def getNodeInNthDistance(self, ptr: Optional[ListNode], n: int) -> Optional[ListNode]:
	while ptr and n > 0:
		ptr = ptr.next
		n -= 1
	return ptr

Let's place the Left pointer before N nodes from the Right.
To do so, initialize a Dummy Node and attach it with the Head. Then put the Left pointer on the Dummy Head. Let's visualize

Awesome, we placed our Left and Right pointer in such a way that there are N nodes in between them.

# Definition for singly-linked list.
# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
	dummy = ListNode(next=head)
	left = dummy
	right = self.getNodeInNthDistance(head, n)

Now let's forward both of the pointer one node at a time until the Right pointer reaches at NULL

while right:
	left = left.next
	right = right.next

Now the Right pointer has reached at NULL and the Left pointer has reached at the Node before Nth Node from the End. Now connect Left node with it's next of next node.

left.next = left.next.next
That's it, let's write the whole code.

Complete Code Snippet

class Solution:
	def getNodeInNthDistance(self, ptr: Optional[ListNode], n: int) -> Optional[ListNode]:
		while ptr and n > 0:
			ptr = ptr.next
			n -= 1
		return ptr
	def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
		dummy = ListNode(next=head)
		left = dummy
		right = self.getNodeInNthDistance(head, n)
		
		while right:
			left = left.next
			right = right.next
		
		# connect left with next of it's next node
		left.next = left.next.next
		return dummy.next

Thanks for Stopping by! Happy Leet coding

Connect with me on