Python数据结构之翻转链表

对于“Python数据结构之翻转链表”的完整攻略，我会按照以下顺序进行讲解：

1.什么是链表？

2.如何翻转链表？

3.示例1：翻转一个简单的链表

4.示例2：翻转一个带环的链表

5.如何在Python中实现翻转链表？

接下来，我会详细讲解每个部分。

什么是链表？

链表是一种数据结构，它由一系列的节点组成，每个节点包含了数据和指向下一个节点的指针。链表有很多种类型，包括单向链表、双向链表和循环链表等。链表相比于数组，有其自身的优势和劣势，我们可以在具体使用的时候选择不同的数据结构。

如何翻转链表？

翻转链表是指将链表中的节点按照相反的顺序重新排列，比如如果原先的链表是1-2-3-4-5，那么翻转后的链表就是5-4-3-2-1。

翻转链表的基本思路是遍历链表并将各个节点的指针反转。具体来说，我们可以设置三个指针prev，curr和next，初始化时，prev指向None，curr指向链表的头节点，next指向curr的下一个节点。然后，我们需要在循环中对curr节点的指针进行反转，即将该节点的next指针指向prev，同时更新prev、curr和next指针。最后，返回prev指针，即新链表的头节点。

示例1：翻转一个简单的链表

假设我们有一个简单的链表：1-2-3-4-5。我们可以使用如下代码翻转该链表：

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

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

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

# 输出原链表
curr = head
while curr:
    print(curr.val, end=" ")
    curr = curr.next
# 输出：1 2 3 4 5

# 翻转链表
new_head = reverseList(head)

# 输出新链表
curr = new_head
while curr:
    print(curr.val, end=" ")
    curr = curr.next
# 输出：5 4 3 2 1

示例2：翻转一个带环的链表

接下来，我们考虑一个较为复杂的情况，我们在链表中加入一个环，其中一部分节点形成环。比如链表是1-2-3-4-5，并且节点3和节点5形成了环路，即节点5的next指针指向节点3。

我们可以使用以下代码实现该功能：

# 创建带环的链表
head = ListNode(1)
node1 = ListNode(2)
node2 = ListNode(3)
node3 = ListNode(4)
node4 = ListNode(5)
head.next = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # 添加环

# 输出原链表
curr = head
for i in range(10):
    print(curr.val, end=" ")
    curr = curr.next
# 输出：1 2 3 4 5 3 4 5 3 4

# 翻转链表
new_head = reverseList(head)

# 输出新链表
curr = new_head
for i in range(10):
    print(curr.val, end=" ")
    curr = curr.next
# 输出：4 3 2 1 5 3 4 5 3 4

从上面的代码可以看出，翻转链表的函数能够正确处理带环的链表，而且在翻转后仍然能够保留原来的环路。

如何在Python中实现翻转链表？

现在，我们将翻转链表的代码封装到一个函数中。同时，我们也需要实现一个函数用来创建链表。具体如下：

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

def createList(vals: List[int]) -> ListNode:
    # 创建链表
    head = ListNode(vals[0])
    curr = head
    for val in vals[1:]:
        curr.next = ListNode(val)
        curr = curr.next
    return head

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

现在，我们就可以使用这些函数对任意的链表进行翻转了，比如：

# 创建链表
head = createList([1, 2, 3, 4, 5])

# 输出原链表
curr = head
while curr:
    print(curr.val, end=" ")
    curr = curr.next
# 输出：1 2 3 4 5

# 翻转链表
new_head = reverseList(head)

# 输出新链表
curr = new_head
while curr:
    print(curr.val, end=" ")
    curr = curr.next
# 输出：5 4 3 2 1

总之，翻转链表是一个常见的面试问题，掌握该问题的解决方法对于编程人员具有非常重要的意义。