Mock 2 — Linked Lists (45 min)

Download and complete the starter notebook

Use the Download starter notebook button on this lesson. Open the .ipynb in JupyterLab, Jupyter Notebook, or another compatible Python 3 environment. Work in a saved copy, complete the TODOs and reflection cells, run the public checks, add the requested tests, then upload that completed .ipynb to this lesson. Do not submit a blank starter. The notebook intentionally contains no answer key or private reviewer rubric.

Instructions

You have 45 minutes. Use this node contract unless your language needs an equivalent:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Complete the notebook's three function cells and the pointer trace for cycle detection. State time and auxiliary-space complexity. For reverse and merge, inputs are acyclic. Merge may relink and reuse the input nodes; allocating replacement nodes is also acceptable if values and order are preserved. Inputs may be empty.

Problem 1 — Reverse a Linked List (Easy, about 10 minutes)

Implement reverse_list(head) and return the new head. Test empty, one-node, and multi-node lists.

Problem 2 — Find the Start of a Cycle (Medium, about 15 minutes)

Implement detect_cycle(head). Return the node object where the cycle begins, or None if the list is acyclic. A cycle may begin at the head. Compare nodes by identity, not just their values.

Example shape: 1 → 2 → 3 → 4 → 5, with node 5 pointing back to node 2; return the existing node whose value is 2.

Problem 3 — Merge K Sorted Lists (Hard, about 20 minutes)

Implement merge_k_lists(lists) for K sorted singly linked lists. Return one sorted list containing every input value with its original multiplicity. Empty list collections and empty individual lists are valid. Equal-valued nodes may appear in either order.

Example: [[1,4,5], [1,3,4], [2,6]] → 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.

Submit the completed notebook

• Download this lesson's starter Jupyter notebook, complete the requested functions, and upload the saved .ipynb file here.
• Keep your implementation, added tests, complexity reasoning, and interview reflection in the notebook. No separate source file or NOTES.md is required.
• Do not upload the untouched starter. Public checks are examples, not a complete test suite; add the edge cases requested in the notebook.
• The downloadable notebook contains no reference solutions or reviewer rubric. Notebook outputs are not used as proof of correctness; the reviewer checks your submitted source and written reasoning.