python写一个单链表逆序算法

以下是Python实现的单链表逆序算法：

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

这里我们定义了一个`ListNode`类来表示链表中的节点，每个节点由一个值`val`和一个指向下一个节点的指针`next`组成。`reverseList`函数接收一个链表的头节点`head`作为输入，返回一个逆序后的链表的头节点。

我们使用三个指针`prev`、`curr`和`next_node`来完成链表的逆序。初始时，`prev`指向`None`，`curr`指向头节点`head`，`next_node`指向`curr`的下一个节点。在循环中，依次将`curr`的`next`指针指向`prev`，然后更新`prev`、`curr`和`next_node`的值。当`curr`为空时，循环结束，此时`prev`指向原链表的尾节点，即逆序后的链表的头节点。最后返回`prev`即可。

相关问题

利用栈实现单链表逆序的算法

以下是利用栈实现单链表逆序的算法：

1. 创建一个空栈。
2. 遍历单链表，将每个节点依次压入栈中。
3. 弹出栈顶节点，并将其链接到新的链表中。
4. 重复步骤3，直到栈为空。
5. 返回新的链表，即为逆序后的单链表。

示例代码如下所示：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

def reverse_linked_list(head):
    stack = []
    current = head

    # 将链表节点压入栈中
    while current:
        stack.append(current)
        current = current.next

    # 弹出栈顶节点，并链接到新的链表中
    new_head = Node()
    current = new_head
    while stack:
        node = stack.pop()
        current.next = node
        current = current.next

    # 设置新链表的尾节点的next为None
    current.next = None

    return new_head.next

用时间复杂度为n的算法，将一个长度为n的单链表逆序排列。

可以使用迭代法或递归法来实现单链表的逆序排列。

迭代法的实现思路是，依次将每个节点的 next 指针指向它的前驱节点。具体步骤如下：

1. 定义三个指针 prev、curr 和 next，分别指向当前节点的前驱节点、当前节点和当前节点的后继节点。
2. 遍历单链表，对于当前节点，将它的 next 指针指向它的前驱节点 prev，然后将 prev、curr 和 next 指针同时向右移动一个节点。
3. 当遍历到最后一个节点时，将它的 next 指针指向它的前驱节点 prev，并将它设为新的头节点。

代码如下：

def reverseList(head):
    if not head or not head.next:
        return head
    prev, curr, next = None, head, head.next
    while curr:
        curr.next = prev
        prev = curr
        curr = next
        next = next.next if next else None
    return prev

递归法的实现思路是，先递归地反转后续节点，然后将当前节点的 next 指针指向它的后继节点的后继节点。具体步骤如下：

1. 递归地反转当前节点后面的节点。
2. 将当前节点的 next 指针指向它的后继节点的后继节点。
3. 返回新的头节点。

代码如下：

def reverseList(head):
    if not head or not head.next:
        return head
    newHead = reverseList(head.next)
    head.next.next = head
    head.next = None
    return newHead

这两种方法的时间复杂度均为 O(n)，空间复杂度为 O(1)。