Date: 2026-06-06
Time: 18:53
reverse-linked-list/solution.pyThis file is the self-contained solution for LeetCode #206 — Reverse Linked List. It owns the problem's data structure (ListNode), two solution variants (iterative and recursive), test helpers for conversion between Python lists and linked lists, and a full unit test suite. It follows the repo-wide pattern where each problem directory holds a solution.py that serves as both implementation and test module.
ListNode — The singly linked list node. Two fields: val: int and next: Optional[ListNode]. This is a local definition (not imported from a shared module), which keeps the solution self-contained but means the class is duplicated across every linked-list problem in the repo.
reverselist(head) — Iterative reversal. Uses three pointers (prev, curr, nextnode) to reverse links in a single pass. Returns the new head (formerly the tail). O(n) time, O(1) space.
reverselistrecursive(head) — Recursive reversal. Base case: empty list or single node returns head. Recursive case: reverses everything after head, then rewires head.next.next = head and head.next = None to append the current node at the tail of the already-reversed suffix. O(n) time, O(n) stack space.
tolinkedlist(vals) / tolist(head) — Bidirectional conversion helpers. tolinked_list uses a dummy-head pattern to simplify construction. These exist to bridge between Python lists (easy to assert on) and linked lists (what the solution operates on).
TestReverseList — Six test cases exercising both implementations via runboth, which uses unittest.subTest to run each function variant independently with clear failure attribution.
runboth avoids duplicating test logic for the iterative vs. recursive variants. subTest labels failures by function name.tolinkedlist allocates a sentinel ListNode(0) and returns dummy.next, sidestepping the "is this the first node?" conditional.runboth call builds a fresh linked list, so mutations from reversal don't leak between subtests.Imports: Only stdlib — _future_.annotations (for Optional[ListNode] forward-ref syntax), typing.Optional, unittest. No external or project-internal imports.
Imported by: The massive Imported By list in the prompt is misleading — those are test files from *other* problems that likely share a test runner harness, not files that import symbols from this module. The real direct consumer is reverse-linked-list/test_solution.py.
For the iterative path (reverse_list):
1. Initialize prev = None, curr = head.
2. Loop while curr is not None: save curr.next, point curr.next back to prev, advance prev and curr forward.
3. When curr is None, prev points to what was the last node — now the new head.
For the recursive path (reverselistrecursive):
1. If head is None or a lone node, return it (base case).
2. Recurse on head.next — this returns the new head of the fully-reversed tail.
3. The current head.next still points to the last node of the reversed tail. Set head.next.next = head to append head, then sever head.next = None.
4. Return new_head (unchanged through the unwind).
reverse_list completes, every node's .next pointer has been reversed. The original tail is the new head; the original head has .next == None.reverselistrecursive requires that the list is acyclic — a cycle would cause infinite recursion.tolinkedlist([]) returns None, matching the LeetCode convention for empty lists.None. Both solutions assume valid input (a well-formed acyclic linked list or None). The tests rely on unittest assertions — no custom exception types. A cyclic input would hang reverselist and stack-overflow reverselist_recursive, but that's outside the problem's contract.