python反转单链表算法题

使用python实现反转单链表，可以分为迭代和递归两种方法。

迭代解法

迭代解法需要用到三个指针，分别是pre、cur和tmp。pre指向已翻转的链表，cur指向待翻转的链表，tmp用于保存cur的下一个节点。具体步骤如下：

1. 定义pre为None，并将cur指向head节点。
2. 遍历链表，当cur不为None时执行以下操作：
3. 将tmp指向cur的下一个节点。
4. 将cur的next指针指向pre节点。
5. 将pre指向当前节点cur。
6. 将cur指向tmp。
7. 遍历结束时，pre指向已经反转后的链表。返回pre作为新链表的头节点即可。

示例：

假设链表为1 -> 2 -> 3 -> 4 -> 5，进行反转操作后，链表变为5 -> 4 -> 3 -> 2 -> 1。

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

def reverseList(head: ListNode) -> ListNode:
    pre = None
    cur = head
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

递归解法

递归解法相对于迭代解法更为简洁，思路也更为清晰。递归解法的主要思路是先递归到链表的末端，然后再依次反转链表。具体步骤如下：

1. 如果链表为空或仅包含一个节点，则返回该链表。
2. 递归到链表的末端，返回新的链表头节点。
3. 依次反转每个节点的next指针指向前一个节点。
4. 返回新的链表头节点。

示例：

假设链表为1 -> 2 -> 3 -> 4 -> 5，进行反转操作后，链表变为5 -> 4 -> 3 -> 2 -> 1。

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

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    p = reverseList(head.next)
    head.next.next = head
    head.next = None
    return p

以上就是python反转单链表算法题的两个解法，递归解法相比迭代解法的代码量更少且更易理解，但是递归会消耗较多的堆栈空间，当链表过长时，容易导致栈溢出的问题。