Python单链表逆序

Python中的单链表逆序可以通过改变节点之间的指针指向来实现。具体步骤如下：

1. 定义一个函数，接受一个链表的头节点作为参数。
2. 初始化三个指针：prev指向None，curr指向头节点，next指向None。
3. 使用while循环遍历链表，直到curr为None。
4. 在循环中，先将next指向curr的下一个节点，然后将curr的下一个节点指向prev，实现指针的反转。
5. 将prev指向curr，curr指向next，继续遍历下一个节点。
6. 循环结束后，将链表的头节点指向prev，完成链表的逆序。
7. 返回逆序后的链表头节点。

下面是Python代码示例：

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

def reverseLinkedList(head):
    prev = None
    curr = head
    next = None

    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    return prev

相关问题

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`即可。

用时间复杂度为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)。