A fixed gap between two pointers

Counting from the end without knowing the length: start one pointer early and keep the distance.

Key idea

The gap never changes

Position from the end is awkward because you only discover the end by reaching it. The two-pass answer counts the length, then walks again. The one-pass answer keeps two pointers a fixed distance apart.

Advance the lead pointer k steps first. Then move both together. When the lead reaches the end, the trailing pointer is exactly k behind it, which is k from the end.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def kth_from_end(head, k):19    lead = head20    for _ in range(k):21        if lead is None:22            return None            # the list is shorter than k23        lead = lead.next24 25    trail = head26    while lead:27        lead = lead.next28        trail = trail.next29    return trail30 31print(kth_from_end(build([1, 2, 3, 4, 5]), 2).val)32print(kth_from_end(build([1, 2]), 5))

Find the bug· 5 min

Find the off-by-one

This is meant to insert a new node immediately before the kth node from the end. On a three-node list with k equal to 1 the new node lands in the wrong place. Click the line that causes it.

Click the line you think is wrong

Problem· 22 min

Remove Nth Node From End Of List

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def kth_from_end(head, k):19 lead = head20 for _ in range(k):21 if lead is None:22 return None # the list is shorter than k23 lead = lead.next24 25 trail = head26 while lead:27 lead = lead.next28 trail = trail.next29 return trail30 31print(kth_from_end(build([1, 2, 3, 4, 5]), 2).val)32print(kth_from_end(build([1, 2]), 5))