递归法python写反转链表伪代码

递归法的反转链表的伪代码如下：

def reverse_list(head):
    # 如果链表为空或只有一个节点，则直接返回
    if head is None or head.next is None:
        return head

    # 反转后的链表头节点
    new_head = reverse_list(head.next)
    
    # 将当前节点的下一个节点的 next 指针指向当前节点
    head.next.next = head
    
    # 当前节点的 next 指针置空
    head.next = None

    return new_head

相关问题

python递归实现链表反转

以下是Python递归实现链表反转的代码示例：

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

以上代码中，我们定义了一个`ListNode`类来表示链表节点，`Solution`类中的`reverseList`方法用于反转链表。在方法中，我们首先判断链表是否为空或者只有一个节点，如果是，则直接返回该链表。否则，我们递归调用`reverseList`方法，将当前节点的下一个节点作为参数传入，得到反转后的新链表头节点。然后，我们将当前节点的下一个节点的`next`指针指向当前节点，将当前节点的`next`指针置为`None`，最后返回新链表的头节点。

1025python反转链表

可以使用迭代或递归来反转一个链表。

迭代方法：

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

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

递归方法：

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

这两种方法的时间复杂度都是 $O(n)$，空间复杂度是 $O(1)$ 或 $O(n)$（递归方法的空间复杂度是 $O(n)$）。