链表反转

链表反转是计算机科学中一个常见的问题，涉及到对链表数据结构的操作。链表是一种线性数据结构，其中每个元素（节点）包含数据部分和指向下一个节点的指针。链表反转的目标是将链表中的元素顺序颠倒过来。

基础概念

链表：一种数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
节点：链表中的基本单元，包含数据域和指针域。
头节点：链表的第一个节点。
尾节点：链表的最后一个节点，其指针域为空或指向空。

类型

单链表反转：最常见的情况，每个节点只有一个指向下一个节点的指针。
双链表反转：每个节点有两个指针，分别指向前一个节点和后一个节点。

应用场景

算法设计：在许多算法中，如深度优先搜索（DFS），需要反向遍历链表。
数据结构操作：在某些情况下，需要临时改变数据的顺序，例如在实现栈的pop操作时。

示例代码（单链表反转）

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

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next  # 暂存下一个节点
        current.next = prev       # 反转当前节点的指针
        prev = current            # 移动prev和current指针
        current = next_node
    return prev  # prev现在是新的头节点

# 创建链表 1 -> 2 -> 3 -> None
head = ListNode(1, ListNode(2, ListNode(3)))

# 反转链表
new_head = reverse_list(head)

# 打印反转后的链表
current = new_head
while current:
    print(current.value, end=" -> ")
    current = current.next
# 输出: 3 -> 2 -> 1 -> None