Description

The gap method is a variant of the Fixed Sliding Window for linked lists.
?
It works by moving the leading node forward till you reach the gap size, then moving them both in unison. Technically you could also do this as a variant of Variable Sliding Window

Reach for when

You need to find an element k away from the end, or need a sliding window style solution.

Runtime

O(n)

Visualization

Pseudocode

tail = head
leader = head
for gapSize:
	leader = leader.next
while leader:
	tail = tail.next
	leader = leader.next

Code

def remove_nth_from_end(head, n):
	dummy = ListNode(0, head)     # dummy so removing the head is uniform
	tail = dummy
	leader = dummy
	for _ in range(n):            # open a gap of n between them
		leader = leader.next
	while leader.next:            # move both until leader is on the last node
		tail = tail.next
		leader = leader.next
	tail.next = tail.next.next    # tail sits just before the target → skip it
	return dummy.next