Python算法题-链表反转详解

1. 题目描述

给定一个单链表，将其翻转。例如：

输入: 1 -> 2 -> 3 -> 4 -> None

输出: 4 -> 3 -> 2 -> 1 -> None

2. 解法分析

链表是一种动态数据结构，它不要求内存必须按照线性顺序连续分布，相对于数组来说，它更加灵活。

链表的每一个元素都有一个指向下一个元素的指针，也就是所谓的"next"指针。当一条链表反转时，每个元素的next指针都指向上一个元素，最后一个元素的next指针为空。

例如给定一个链表 1 -> 2 -> 3 -> 4 -> None，反转操作后应该变成 4 -> 3 -> 2 -> 1 -> None。

3. 代码实现

下面是Python3的代码实现：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur is not None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

以上代码中，我们需要定义一个ListNode类，表示我们要翻转的链表。翻转的算法思路使用了三个指针，分别是pre、cur、tmp。

假设当前的指针为cur，那么下一个节点为cur.next。我们需要保存上一个节点，用pre表示。将当前节点的next指向保存的上一个节点pre，然后将指针后移。重复进行以上操作，直到将链表翻转为止。

4. 示例说明

示例1：

我们先创建一个链表1 -> 2 -> 3 -> 4 -> None，然后将其打印出来看一下：

if __name__ == '__main__':
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = None

    s = Solution()
    head = s.reverseList(l1)
    while head:
        print(head.val, end='->')
        head = head.next

输出结果为4 -> 3 -> 2 -> 1 -> None，符合我们的预期。

示例2：

我们再创建一个链表5 -> 6 -> None，然后将其打印出来看一下：

if __name__ == '__main__':
    l5 = ListNode(5)
    l6 = ListNode(6)
    l5.next = l6
    l6.next = None

    s = Solution()
    head = s.reverseList(l5)
    while head:
        print(head.val, end='->')
        head = head.next

输出结果为6 -> 5 -> None，同样符合我们的预期。

5. 总结

本文讲解了链表的反转操作，属于经典的算法题目，需要掌握链表的基本操作以及指针的使用技巧。在实际工作、学习中，链表操作也是非常常见的数据结构。