Practice: Removing Every Expired Ticket

Walk a singly linked list of tickets and unlink each one past its date.

Removing every node that fails a test from a singly linked list practises rewiring at the head, in the middle and at the tail in one walk. This card covers it as an exercise, with an answer to check yours against.

A singly linked list holds five tickets in order, each with a number and the day it expires: 101 expires on day 3, 102 on day 9, 103 on day 2, 104 on day 12 and 105 on day 5. Today is day 6, and a ticket whose day is before today has expired. Each node has number, expires and next.

Say which tickets remain and which one is the tail afterwards.
Write remove_expired(head, today) so that it unlinks every expired ticket and returns the new head and the new tail.
Name the cases that need their own handling, and state the time and extra space.

An answer: what remains, a function with two loops, and its cost

Tickets 102 and 104 remain, and 104 is the tail. Three cases differ. An expired head has no node before it, so the head itself moves on. An expired ticket in the middle is skipped by the node before it. An expired tail leaves the node before it as the last one, which becomes the new tail.

expired_tickets.pypy

from dataclasses import dataclass


@dataclass
class Ticket:
    number: int
    expires: int
    next: Ticket | None = None


def remove_expired(head: Ticket | None, today: int) -> tuple[Ticket | None, Ticket | None]:
    while head is not None and head.expires < today:
        head = head.next
    tail = head
    current = head
    while current is not None and current.next is not None:
        if current.next.expires < today:
            current.next = current.next.next
        else:
            current = current.next
        tail = current
    return head, tail


def numbers(head: Ticket | None) -> list[int]:
    items: list[int] = []
    while head is not None:
        items.append(head.number)
        head = head.next
    return items


head: Ticket | None = None
for number, expires in reversed([(101, 3), (102, 9), (103, 2), (104, 12), (105, 5)]):
    head = Ticket(number, expires, head)
print(f"before: {numbers(head)}")
head, tail = remove_expired(head, today=6)
print(f"after:  {numbers(head)}, tail {'none' if tail is None else tail.number}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

before: [101, 102, 103, 104, 105]
after:  [102, 104], tail 104

The first loop moves the head past any run of expired tickets at the front, and returns None for both ends when every ticket has expired. The second keeps current on a ticket that stays and looks one ahead, because unlinking needs the node before; it moves on only when the next ticket stays, so two expired tickets in a row are both removed. Each ticket is checked once, so the time is O(n), and the extra space is O(1).

← → move through sections and cards