Closed Tram Stop

Mediumtwo pointersAlso known as Remove Nth Node From End of List

A tram line's route is stored as a chain of stops, from the first stop to the terminus. Each stop only knows the next stop on the line.

Roadworks close a stop, and the notice from the city counts from the far end: "the 3rd stop before the end of the line, counting the terminus as 1st". The route system must skip that stop. It reads the route once, from the front, because the route can be long and is shared with other systems.

Your task

Write closeStop(head, k). Remove the k-th node counting from the end of the list (k = 1 is the last node) and return the head of the updated list.

If the removed stop was the first one, the head changes. If it was the only stop, return an empty list (null / None). Try to do it in a single pass.

closeStop(head: ListNode, k: int) → ListNode

Examples

Example 1

Input

head = [11, 24, 35, 47, 52]
k = 2

Output

[11, 24, 35, 52]

Why

Counting from the end, 52 is 1st and 47 is 2nd. Remove 47, so 35 now points straight to 52.

Example 2

Input

head = [11, 24, 35]
k = 3

Output

[24, 35]

Why

The 3rd stop from the end of a 3-stop line is the first stop. There is no stop before it to relink, so the new head is 24.

Constraints

1 ≤ number of stops ≤ 5,000
1 ≤ k ≤ number of stops
Stop ids are integers and may repeat.

Start with brute force

Walk the whole route once to count the stops, n. The closed stop is number n - k + 1 counting from the front, so walk again to the stop just before it and relink that one.

That is O(n) and correct, so the problem is not speed in big-O terms. It reads the route twice, though, and the city's system only wants one read. The gap trick does the same job in one pass, and the same idea finds "the k-th last item" of any stream you can read only once.

Hints

0 of 4 shown

Hint 1
To remove a node from a singly linked list, which node do you actually need to be standing on?
Hint 2
You need the node just before the closed stop, so you can set its next to skip one. If you knew the length n, that node is n - k steps in. Can you find it without knowing n?
Hint 3
Imagine two walkers on the route with exactly k stops between them. When the front walker steps off the end, where is the back walker?
Hint 4
Put a dummy node before the head (it handles removing the first stop). Move lead forward k steps from the dummy, then move lead and trail together until lead.next is null. Now trail.next is the closed stop: set trail.next = trail.next.next and return dummy.next.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Keep two pointers a fixed distance apart. When the front one reaches the last stop, the back one is exactly k stops behind it, which is the stop just before the one to remove.

Trace 11 → 24 → 35 → 47 → 52 with k = 2. Start both pointers on a dummy node D placed before 11.

Move lead 2 steps: D → 11 → 24. lead = 24, trail = D.
lead.next exists. Move both: lead = 35, trail = 11.
Move both: lead = 47, trail = 24.
Move both: lead = 52, trail = 35. Now lead.next is null, so stop.
trail.next is 47. Set 35's next to 52. Return dummy.next: 11 → 24 → 35 → 52.

Why the dummy: when k equals the length, the stop to remove is the head, and the node "before" it does not exist. With a dummy, trail stays on D and D.next = D.next.next removes the head like any other node. Forgetting this case is the most common bug here.

Reference solution

function closeStop(head, k) {
  const dummy = new ListNode(0, head); // lets us remove the first stop too
  let lead = dummy;
  let trail = dummy;
  for (let i = 0; i < k; i++) lead = lead.next; // open a gap of k
  while (lead.next !== null) {
    lead = lead.next;
    trail = trail.next;
  }
  trail.next = trail.next.next; // skip the closed stop
  return dummy.next;
}

def close_stop(head, k):
    dummy = ListNode(0, head)  # lets us remove the first stop too
    lead = trail = dummy
    for _ in range(k):  # open a gap of k
        lead = lead.next
    while lead.next is not None:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next  # skip the closed stop
    return dummy.next

TimeO(n)lead walks the list once; trail follows behind it.

SpaceO(1)A dummy node and two pointers.

Learn the idea: Linked Lists

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code