头插法与迭代反转链表：详解两种链表反转方法及 Python 代码示例

链表反转是数据结构中常见的操作，主要方法有两种：头插法和迭代反转。本文将详细介绍这两种方法的原理、区别以及相应的 Python 代码示例。

1. 头插法

头插法是一种通过在新建链表的头部插入节点的方式来反转链表的方法。具体步骤如下：

创建一个新的空链表。
遍历原链表，每次取出一个节点，将其插入新链表的头部。
最后返回新链表即可。

代码示例 (Python):

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

def reverse_list(head):
    new_head = None
    while head:
        temp = head.next
        head.next = new_head
        new_head = head
        head = temp
    return new_head

2. 迭代反转链表

迭代反转链表是一种通过改变指针指向的方式来实现链表反转的方法。具体步骤如下：

创建三个指针，分别指向当前节点、当前节点的前一个节点和当前节点的后一个节点。
遍历链表，每次将当前节点的指针指向前一个节点，然后更新三个指针的位置。
最后返回反转后的链表的头部。

代码示例 (Python):

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

总结

头插法构建新的反转链表，而迭代反转链表修改原链表指针指向。
头插法需要额外空间存储新链表，而迭代反转链表不需要额外空间。
迭代反转链表效率更高，时间复杂度为 O(n)，空间复杂度为 O(1)。

通过理解这两种方法的原理和代码示例，读者可以更好地掌握链表反转的技巧，并根据实际情况选择合适的方法进行实现。