Reverse a linked list implemented in python3

reverse_linked_list.py

#!/usr/bin/env python

# 反转一个单链表。示例:
# 输入: 1 --> 2 --> 3 --> 4 --> 5 --> None
# 输出: 5 --> 4 --> 3 --> 2 --> 1 --> None

from typing import Any, List, Optional

ListNode = Optional["Node"]


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


class LinkedList:
    def __init__(self, head: ListNode):
        self.head = head

    @classmethod
    def create(cls, values: List[Any]):
        head = None

        # 采用往头部添加新节点的方法，需要传入跟链表顺序相反的序列
        for i in reversed(values):
            new_head = Node(i)
            new_head.next = head
            head = new_head

        return cls(head)

    def reverse_loop(self):
        # 已反转部分的头节点
        reversed_head = None
        head = self.head

        while head:  # 剩余部分的头节点，也是当前在处理的节点
            # 保存下一个节点，以免更新当前节点指针方向后无法找到下一个节点
            next = head.next
            # 反转当前节点的指针方向
            head.next = reversed_head
            # 更新已反转部分的头节点为当前节点
            reversed_head = head
            # 更新当前节点为之前保存下来的下一个节点
            head = next

        self.head = reversed_head

    def reverse_recursive(self):
        def _reverse(head: ListNode):
            current = head
            # 递归出口：空链表 或者 非空链表的最后一个节点
            if current is None or current.next is None:
                return current

            # new_head 一旦返回就一直不变，每次递归出栈传递的都是一个不变的值
            # 因为下面没有对其进行任何更改的操作，只在最后返回了它
            new_head = _reverse(current.next)
            # 反转下一个节点的指针方向，使其指向自己
            current.next.next = current
            # 这个每次递归都得执行一次，理论上只有最后一次执行就行，但是在递归的情况下，好像又没法优化之。
            current.next = None

            return new_head

        self.head = _reverse(self.head)

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.val
            current = current.next

    def __str__(self):
        r = ""
        for v in self:
            r += "%s -> " % v
        r += "None"
        return r


def test():
    # 测试循环和递归两种实现
    for impl in ('reverse_loop', 'reverse_recursive'):
        print("# Using implementation: %s" % impl)
        # 测试 Node 数为 0 1 5 三种情况
        for n in [0, 1, 5]:
            print("## The number of nodes: %d" % n)
            values = list(range(1, 1+n))
            linked_list = LinkedList.create(values)
            print(linked_list)
            assert list(linked_list) == values
            getattr(linked_list, impl)()
            print(linked_list)
            print()
            assert list(linked_list) == list(reversed(values))

    print("All tests passed!")

if __name__ == "__main__":
    test()