Python实现单链表反转：高效算法及代码示例

本文将介绍如何使用Python实现单链表的反转，并提供详细的代码示例和算法解释。

问题描述：

给定一个单链表的头结点 pHead (该头节点是有值的), 长度为 n, 反转该链表后，返回新链表的表头。

数据范围:

• 0 ≤ n ≤ 1000

要求:

• 空间复杂度 O(1)* 时间复杂度 O(n)

示例:

输入链表: {1,2,3}

反转后: {3,2,1}

**代码实现:**pythonclass ListNode: def init(self, val=0, next=None): self.val = val self.next = next

def reverseLinkedList(pHead): ''' 反转单链表

Args:        pHead: ListNode, 链表头结点

Returns:        ListNode: 反转后的链表头结点    '''    if not pHead or not pHead.next:        return pHead

prev = None    curr = pHead

while curr:        temp = curr.next        curr.next = prev        prev = curr        curr = temp

return prev

示例链表: 1 -> 2 -> 3pHead = ListNode(1)pHead.next = ListNode(2)pHead.next.next = ListNode(3)

反转链表reversed_head = reverseLinkedList(pHead)

打印反转后的链表result = []curr = reversed_headwhile curr: result.append(curr.val) curr = curr.next

print(result) # 输出: [3, 2, 1]

算法解释:

该算法使用迭代的方式进行链表反转，具体步骤如下:

1. 初始化三个指针: prev 指向前一个节点 (初始值为 None), curr 指向当前节点 (初始值为 pHead), temp 指向下一个节点。2. 遍历链表，每次迭代执行以下操作: * 将 temp 指向当前节点的下一个节点: temp = curr.next * 将当前节点的 next 指针指向前一个节点: curr.next = prev * 将 prev 指针移动到当前节点: prev = curr * 将 curr 指针移动到下一个节点: curr = temp3. 循环结束后，prev 指针指向反转后的链表头结点，返回 prev。

时间复杂度分析:

该算法只遍历了链表一次，因此时间复杂度为 O(n)。

空间复杂度分析:

该算法只使用了常数个额外变量，因此空间复杂度为 O(1)。