Python函数实现链表的反转

链表是一种常见的数据结构，它由一个个的节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。

链表的反转是指将链表中的节点按照相反的顺序重新排列。例如，给定一个链表1->2->3->4->5，经过反转之后，链表变为5->4->3->2->1。

在Python中，可以用函数来实现链表的反转。下面是一个实现链表反转的函数：

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

def reverseList(head):
    # 边界条件判断
    if not head or not head.next:
        return head
    
    # 初始化三个指针，分别指向当前节点、前一个节点和后一个节点
    curr = head
    prev = None
    next = None
    
    while curr:
        # 先记录下一个节点
        next = curr.next
        # 将当前节点的next指针指向前一个节点
        curr.next = prev
        # 更新prev和curr指针，继续遍历
        prev = curr
        curr = next

    # 返回反转后的头节点
    return prev

接下来我们测试一下这个函数，看看能否正确地反转链表：

# 创建链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 打印原始链表
curr = node1
while curr:
    print(curr.val, end="->")
    curr = curr.next

# 反转链表
new_head = reverseList(node1)
print()

# 打印反转后的链表
curr = new_head
while curr:
    print(curr.val, end="->")
    curr = curr.next

运行结果：

1->2->3->4->5->
5->4->3->2->1->

可以看到，链表的反转函数成功地将原始链表1->2->3->4->5反转为5->4->3->2->1。

这个函数的时间复杂度是O(n)，其中n是链表的长度。