【20240920每日一题】链表反转

难度

题目

请用熟悉的编程语言编写一下链表反转算法。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_list(head):
    # 初始化prev指针为None,current指针为头节点
    prev = None
    current = head

    # 遍历链表节点
    while current is not None:
        # 保存下一个节点的指针
        next_node = current.next
        # 将当前节点的指针指向prev,实现反转
        current.next = prev
        # 更新prev和current指针
        prev = current
        current = next_node

    # 更新头节点为反转后的最后一个节点
    head = prev
    return head

def print_list(head):
    # 遍历打印链表节点数据
    current = head
    while current:
        print(current.data, end=" ")
        current = current.next
    print()

# 用户输入链表数据
input_data = input("请输入链表数据,以空格分隔:")
data_list = input_data.split()

# 构建链表
head = None
prev_node = None
for data in data_list:
    # 创建新的节点
    new_node = Node(int(data))
    if head is None:
        head = new_node
    else:
        prev_node.next = new_node
    prev_node = new_node

print("原始链表:")
print_list(head)

# 反转链表
new_head = reverse_list(head)

print("反转后的链表:")
print_list(new_head)
1 Like