The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

List Exercises

Next ►
►

The time has come to turn what you've learned into craft. This lesson introduces no new theory: it is a full training session with six progressive exercises that integrate the whole module — from manipulating loose nodes to assembling real pieces of the TaskFlow board with combined operations. Several of them (reversing a linked list, detecting cycles with two pointers, merging sorted lists) are also absolute classics of the technical interview: mastering them is not just passing this module, it is direct professional preparation. Work each exercise in three steps: draw the nodes and arrows on paper, write the code without looking at the solution, and test it with lists of 0, 1, 2, and several elements. Only then compare with the commented solution.

Contents

  1. Starting material: the module's classes
  2. Exercise 1 — Counting and extracting with loose nodes (warm-up)
  3. Exercise 2 — Reversing a linked list in place
  4. Exercise 3 — Detecting a cycle with two pointers (hare and tortoise)
  5. Exercise 4 — Merging two boards sorted by priority
  6. Exercise 5 — Moving a task to another position on the board
  7. Exercise 6 — Complete navigable history with a doubly linked list

Starting material: the module's classes

All the exercises reuse the classes built in the previous lessons; copy them into your working file exactly as they ended up:

  • Node and LinkedList (lesson 02-02): head, tail, size, with insert_front, insert_back, remove, find, __iter__, __len__, __str__.
  • DoubleNode and DoublyLinkedList (lesson 02-03): with insert_back, remove_node, find_node, __iter__, __reversed__.
  • The TaskFlow task is still the usual dict: {"id": ..., "title": ..., "priority": ..., "status": ...}.

A helper function for building test boards quickly:

def board_of(*titles_priorities):
    """Creates a LinkedList of tasks: board_of(("Logo", 2), ("Hotfix", 1))."""
    board = LinkedList()
    for i, (title, priority) in enumerate(titles_priorities, start=1):
        board.insert_back({"id": i, "title": title,
                           "priority": priority, "status": "pending"})
    return board

Common Mistakes and Tips

Before starting, the stumbles you will see most often in these six specific exercises:

  • Losing the reference to the rest of the list while rewiring (especially in exercise 2): the moment you reassign next without first saving where it pointed, the list's tail vanishes. The universal fix is a temporary variable that "holds onto" what you are about to let go.
  • Neglecting head, tail, and size when operating on nodes on your own: if you reverse or move nodes by manipulating arrows, the class's strategic references must end up consistent, or the next insert_back will corrupt the list.
  • Testing only the pretty case. Empty list, one node, two nodes, the element at the head, the element at the tail: each exercise states its edge cases and the solutions handle them explicitly. A list algorithm you haven't tested at the edges is not finished.
  • Comparing nodes with == where is is due (exercise 3 especially): identity and equality are not the same thing, and with duplicated task dicts the difference is a real bug.
  • General tip: in the rewiring exercises (2, 4, and 5), first write on paper the numbered sequence of assignments and validate on the drawing that no needed arrow is lost before being copied. It is the method of the previous lessons, and this is where it pays off.

Exercises

Exercise 1 — Counting and extracting with loose nodes (warm-up). Without using LinkedList (only the Node class and a head variable), write two functions: (a) count_status(head, status), returning how many tasks in the chain have that status; (b) extract_done(head), which removes from the chain every task with status "done" and returns the new head (careful: the done ones may be at the front, in the middle, at the back... or be all of them). Edge cases: an empty chain and a chain where everything is removed.

Exercise 2 — Reversing a linked list in place. Write a reverse() method for LinkedList that reverses the order of the nodes without creating new nodes or auxiliary structures: only by redirecting next arrows. The board A -> B -> C must end up C -> B -> A, with head, tail, and the traversal consistent. Required cost: O(n) in time and O(1) in extra space. Hint: traverse with three references (prev, current, next_node). In TaskFlow: viewing the board "from the last tasks to the first" without building a copy.

Exercise 3 — Detecting a cycle with two pointers (hare and tortoise). A bug while programming a circular list (lesson 02-04) can leave an accidental cycle in a board that should be linear: the traversal never ends. Write has_cycle(head) returning True/False using Floyd's algorithm: two pointers advancing at once, one hop by hop (the tortoise) and the other two by two (the hare); if there is a cycle, the hare will eventually catch the tortoise; if not, the hare will reach None. Auxiliary memory proportional to the list is forbidden (no storing visited nodes in a set). Explain in a comment why the algorithm always terminates.

Exercise 4 — Merging two boards sorted by priority. Two teams merge their projects. Each board is a LinkedList already sorted by ascending priority (thanks to the insert_sorted from exercise 2 of lesson 02-02). Write merge(board_a, board_b) returning a new sorted LinkedList with all the tasks, reusing the existing nodes (no creating new nodes: just rewiring), in O(n + m). On equal priority, board A's tasks go first. Edge cases: one or both boards empty. Note: the original boards end up empty after the merge (their nodes now belong to the result); set their head/tail/size to zero so they are not left corrupted.

Exercise 5 — Moving a task to another position on the board. The user drags a task to another position on the board (the star operation of any task manager). Write a method move(self, task_id, new_position) for LinkedList that locates the task by id, unhooks it, and reinserts it at the indicated position (0 = the front), reusing the node (without creating a new one), and returns True if it existed or False if not. Mind: moving to the same position, moving to the head, moving to the tail, a nonexistent id, and leaving head/tail/size consistent. What is the cost?

Exercise 6 — Complete navigable history with a doubly linked list. Complete the TaskHistory from lesson 02-03 with a real browser's behavior: when the user is in the middle of the history (after pressing "back") and visits a new task, all the tasks that lay "forward" are discarded — the new visit becomes the end of the history. Also add where_am_i() (the current task or None) and history_view() (a list of the titles of the whole history, marking the current position with *). Use DoublyLinkedList and truly delete the discarded nodes (with remove_node), keeping size correct. Demonstrate the sequence: visit T1, T2, T3, back, back, visit T4 → the history must be T1, T4.

Solutions

Solution 1:

def count_status(head, status):
    """Classic traversal with a counter. Cost: O(n)."""
    count = 0
    current = head
    while current is not None:
        if current.data["status"] == status:
            count += 1
        current = current.next
    return count

def extract_done(head):
    """Removes every done task. Returns the new head. Cost: O(n)."""
    # Phase 1: advance the head while the first tasks are done
    while head is not None and head.data["status"] == "done":
        head = head.next             # the old head is left with no references
    # Phase 2: bypass the interior done ones with the prev/current pattern
    prev = head
    while prev is not None and prev.next is not None:
        if prev.next.data["status"] == "done":
            prev.next = prev.next.next     # bridge
            # (we do not advance: the new next might also be done)
        else:
            prev = prev.next
    return head

Comments: phase 1 handles the "done tasks at the front" case (including "all done", which returns None, the empty chain). In phase 2, the fine detail is not advancing after bypassing: if two done tasks are consecutive, the new prev.next must be examined too. It is this exercise's most frequent mistake: whoever always advances skips one of every two consecutive done tasks.

Solution 2:

    def reverse(self):
        """Reverses the list by redirecting arrows. O(n) time, O(1) space."""
        prev = None
        current = self.head
        self.tail = self.head            # the old head will be the new tail
        while current is not None:
            next_node = current.next     # 1: hold the rest before letting go
            current.next = prev          # 2: flip the arrow around
            prev = current               # 3: advance prev...
            current = next_node          # 4: ...and current
        self.head = prev                 # the last one visited is the new head

The heart is the loop's quartet, always in that order. Line 1 is the temporary variable that "holds onto" the rest of the list: without it, line 2 would destroy the only path forward. Trace it by hand with A -> B -> C:

graph LR
    subgraph "After the first iteration"
    A["A"] -- "reversed arrow" --> N["None"]
    B["B (current)"] --> C["C"]
    P["prev"] --> A
    end

Each iteration flips exactly one arrow; when current runs out, prev holds the old last node, which becomes the head. Edge cases: with an empty list the loop doesn't run and head/tail stay None; with one node, the arrow A -> None "flips" onto itself with no changes. Verify with print(board) before and after.

Solution 3:

def has_cycle(head):
    """Floyd's algorithm (hare and tortoise). O(n) time, O(1) space."""
    tortoise = head
    hare = head
    while hare is not None and hare.next is not None:
        tortoise = tortoise.next           # advances 1
        hare = hare.next.next              # advances 2
        if tortoise is hare:               # identity, not equality!
            return True
    return False
    # Why does it always terminate? If there is no cycle, the hare finds None in
    # at most n/2 steps. If there is one, both pointers end up inside the cycle,
    # and the hare-tortoise distance SHRINKS BY 1 on every step (the hare
    # closes 2−1=1 per iteration on a finite ring), so it reaches 0:
    # they meet, and the hare cannot "jump over" the tortoise.

Indispensable details: the while condition checks hare and hare.next before the double hop (otherwise, AttributeError at the end of a cycle-free list); the comparison is is because we are looking for the same node — two tasks with identical data are not a cycle. The acid test:

board = board_of(("Logo", 2), ("Server", 2), ("Hotfix", 1))
print(has_cycle(board.head))     # False
board.tail.next = board.head.next   # sabotage: we create a cycle
print(has_cycle(board.head))     # True
# (undo the sabotage before using the board again)
board.tail.next = None

The alternative — "jot down the visited nodes in a set" — is also O(n) in time, but spends O(n) memory; Floyd achieves the same with two references. It is the canonical example of a time-memory trade-off resolved with ingenuity, and a recurring interview question.

Solution 4:

def merge(board_a, board_b):
    """Merges two lists sorted by priority, reusing nodes. O(n+m)."""
    result = LinkedList()
    a = board_a.head
    b = board_b.head

    def attach(node):
        """Appends an existing node at the end of the result (pure rewiring)."""
        node.next = None
        if result.head is None:
            result.head = node
        else:
            result.tail.next = node
        result.tail = node
        result.size += 1

    while a is not None and b is not None:
        if a.data["priority"] <= b.data["priority"]:   # <=: ties go to A
            next_node = a.next      # hold on before rewiring
            attach(a)
            a = next_node
        else:
            next_node = b.next
            attach(b)
            b = next_node

    rest = a if a is not None else b    # one of the two ran out:
    while rest is not None:             # the rest goes in as a block, already sorted
        next_node = rest.next
        attach(rest)
        rest = next_node

    # The originals surrender their nodes: leave them empty and consistent
    board_a.head = board_a.tail = None
    board_a.size = 0
    board_b.head = board_b.tail = None
    board_b.size = 0
    return result

Keys: on each round only the pair of front nodes is compared and the smaller one is attached — which is why the total is O(n + m), each node touched once. The <= (and not <) provides the requested stability: on a tie, A's task goes in first. attach is a mini-insert_back that receives a node instead of creating one: there lies the "reuse without creating". And the final emptying of the originals avoids the two-lists-sharing-nodes bug: if board_a kept its head, modifying the result would also corrupt A. Test: merge(board_of(("Hotfix", 1), ("Logo", 2)), board_of(("DB outage", 1), ("Docs", 3))) → Hotfix(A), DB outage(B), Logo, Docs.

Solution 5:

    def move(self, task_id, new_position):
        """Unhooks the task by id and reinserts it at new_position. O(n)."""
        # Phase 1: locate and unhook (the prev/current pattern from 02-02)
        prev = None
        current = self.head
        while current is not None and current.data["id"] != task_id:
            prev = current
            current = current.next
        if current is None:
            return False                       # nonexistent id
        if prev is None:
            self.head = current.next           # it was the head
        else:
            prev.next = current.next
        if current is self.tail:
            self.tail = prev                   # it was the tail
        self.size -= 1
        current.next = None                    # a loose, clean node

        # Phase 2: reinsert the SAME node at the requested position
        if new_position <= 0 or self.head is None:
            current.next = self.head           # mini insert_front with a node
            self.head = current
            if self.tail is None:
                self.tail = current
        elif new_position >= self.size:
            self.tail.next = current           # mini insert_back with a node
            self.tail = current
        else:
            walker = self.head
            for _ in range(new_position - 1):
                walker = walker.next
            current.next = walker.next
            walker.next = current
        self.size += 1
        return True

A structure in two clean phases: unhook (which is 02-02's remove keeping the node instead of dropping it) and reinsert (which is insert_at receiving a node instead of a data item). The subtle nuance: the position is interpreted over the list without the task — moving to the same position works with no special case, because unhooking and reinserting in the same spot is idempotent. Cost O(n): one pass to locate plus another partial one to get in position; the rewiring, as always, O(1). Test the four edge cases from the statement with a 4-task board and print the board and len after each one.

Solution 6:

class TaskHistory:
    """Complete navigation history on a doubly linked list (TaskFlow)."""
    def __init__(self):
        self.tasks = DoublyLinkedList()
        self.current = None           # node of the current position

    def visit(self, task):
        """New visit: discards the 'forward' part and appends at the end. O(k) discarded."""
        # Discard everything that lay after the current position
        if self.current is not None:
            while self.current.next is not None:
                self.tasks.remove_node(self.current.next)   # O(1) each
        self.tasks.insert_back(task)
        self.current = self.tasks.tail

    def back(self):
        if self.current is not None and self.current.prev is not None:
            self.current = self.current.prev
        return self.where_am_i()

    def forward(self):
        if self.current is not None and self.current.next is not None:
            self.current = self.current.next
        return self.where_am_i()

    def where_am_i(self):
        return self.current.data if self.current is not None else None

    def history_view(self):
        """The history's titles, marking the current position with *."""
        labels = []
        node = self.tasks.head
        while node is not None:
            title = node.data["title"]
            labels.append(f"*{title}*" if node is self.current else title)
            node = node.next
        return labels


# Demonstration of the requested sequence:
def task(i):
    return {"id": i, "title": f"T{i}", "priority": 2, "status": "in_progress"}

h = TaskHistory()
h.visit(task(1)); h.visit(task(2)); h.visit(task(3))
print(h.history_view())     # ['T1', 'T2', '*T3*']
h.back(); h.back()
print(h.history_view())     # ['*T1*', 'T2', 'T3']
h.visit(task(4))
print(h.history_view())     # ['T1', '*T4*']  ← T2 and T3 discarded
print(len(h.tasks))         # 2

The whole module works together in this class: the discarding uses remove_node — O(1) per node because we hold the reference, the moral of 02-03 —, always on self.current.next (which keeps "re-hooking" itself thanks to the removal's bridges, with no indexes or searches); back/forward are O(1) movements along the arrows; and history_view compares nodes with is to mark the position. It is, on a small scale, the same design as Chrome's or Firefox's history: when you navigate from the middle of the history, the discarded future does not come back.

Conclusion

Six exercises and the whole module in play: the prev/current pattern and the bridges (exercise 1), the in-place reversal with its quartet of assignments (2), Floyd's hare and tortoise as a cycle detector in O(1) memory (3), the sorted merge reusing nodes in O(n + m) (4), the move-a-task that combines unhooking and reinserting (5), and the browser history where the doubly linked list's O(1) removals truly pay off (6). If you got here by solving them — and testing them at their edges — linked lists are no longer theory: they are a tool. With module 2 complete, TaskFlow has a board, turn rotation, and a history, and you have the vocabulary of nodes, arrows, and rewirings on which almost everything to come is built. In module 3 we put it to use: the stack, the "last in, first out" structure, which you will be able to implement in a few lines... precisely because you already know how to insert and remove at the head of a linked list in O(1). TaskFlow's undo is waiting for you.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved