链表逆转 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` 函数接收链表的头节点作为参数，使用三个指针 `prev`、`curr` 和 `next_node` 分别表示当前节点的前一个节点、当前节点和当前节点的下一个节点。在遍历链表的过程中，将当前节点的指针指向前一个节点，然后将 `prev` 指针移动到当前节点，`curr` 指针移动到下一个节点，直至遍历完整个链表，最后返回反转后的链表的头节点 `prev`。

相关问题

单向链表逆转: 设已经建立一条单向链表，现欲将各个结点的next域指向其前驱结点，使得单向链表逆转过来

单向链表逆转是指改变每个节点的下一个指针方向，使其指向原来的前一个节点，从而达到整个链表头结点变尾，尾结点变头的效果。以下是递归和迭代两种常见方法实现单向链表逆转：

1. **递归**方法：
- 首先检查链表是否为空或者只有一个元素，这种情况下直接返回。
- 否则，将当前节点的`next`指向前一个节点，并对剩余部分链表递归地进行逆转。

def reverseList(head):
    if head is None or head.next is None:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

2. **迭代**方法：
- 定义两个指针，一个`prev`初始为None，另一个`current`等于头节点。
- 当`current`不为None时，更新`prev`的`next`为`current`，然后将`current`移动到下一个节点。
- 最后返回`prev`作为新的头节点。

def reverseList(head):
    prev = None
    current = head
    while current is not None:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

设计一个算法，逆转一个链表的链接方向

逆转一个链表的链接方向是一个常见的链表操作，通常使用迭代或递归的方法来实现。这里提供一个使用迭代方法的算法：

**迭代法逆转链表：**

1. **定义三个指针**：
- `prev`（前一个节点），初始化为`nullptr`，用于存储当前节点的前一个节点；
- `current`（当前节点），初始化为链表头节点；
- `next_temp`（临时下一个节点），初始化为`nullptr`，用于暂存`current`节点的下一个节点。

2. **遍历链表**：
- 当`current`不为`nullptr`时，执行以下步骤：
a. 将`current`的`next`指针指向`prev`，逆转了`current`节点的链接；
b. 更新`prev`为`current`；
c. 更新`current`为`current->next`，移动到下一个节点；
- 循环直到`current`变为`nullptr`，此时链表已经遍历完成。

3. **返回逆转后的头节点**：
- 最后，`prev`就是逆转后的链表的新头节点。

**伪代码示例：**

function reverseLinkedList(head):
    prev = None
    current = head
    next_temp = None

    while current is not None:
        next_temp = current.next  # 保存当前节点的下一个节点
        current.next = prev      # 将当前节点的next指向前一个节点
        prev = current           # 更新前一个节点为当前节点
        current = next_temp      # 更新当前节点为下一个节点

    return prev  # 返回新头节点