链表逆置

构造链表

class Node(object):
    def __init__(self, value, next) -> None:
        self.value = value
        self.next = next

# 构造只有一个节点的链表，尾部指向自己    
head = Node('Head', None)
last = head

# 填充链表,传入last节点从尾部填充
def add_node(last: Node, count: int):
    for i in range(count):
        # 创建新的临时节点
        tem_node = Node('node%s' %i, None)
        # 将临时节点赋值给传入的节点next
        last.next = tem_node
        # 临时节点变为下一个节点，进入下一次循环
        last = tem_node

add_node(last, 5)
print(head.value)
print(head.next.value)
print(head.next.next.value)
print(head.next.next.next.value)
print(head.next.next.next.next.value)
print(head.next.next.next.next.next.value)

链表逆置操作

# 逆置链表，传入head节点
def reverse_node(head: Node):
    # 当前节点不存在或者仅有一个节点
    # 则不需要逆置
    if not head or not head.next:
        return head
    
    # 初始化空的前向节点
    prev_node = None
    # 将头节点作为当前节点
    current_node = head
    # 将第二位节点作为下一节点
    next_node = head.next
    # 进行逆置
    while True:
        # 将前向节点作为当前节点下一节点
        # 即后向指针改为前向指针
        current_node.next = prev_node
        # 由于最后一个节点的下一节点为none,所以作为退出判断条件
        if not next_node:
            break
        """
        current_node.next = prev_node
        如果将其移至此处则返回的当前节点为None节点
        """

        # 将当前节点改为前一节点
        prev_node = current_node
        # 将下一节点作为当前节点
        current_node = next_node
        # 当前节点的下一节点作为下一节点
        next_node = current_node.next
    return current_node
 
head = reverse_node(head)
print(type(head))
print(head.value)
print(head.next.value)
print(head.next.next.value)
print(head.next.next.next.value)
print(head.next.next.next.next.value)
print(head.next.next.next.next.next.value)