试写一算法,对单链表实现就地逆置。

对单链表实现就地逆置是指在原链表上操作，不需要额外的空间创建新链表，直接改变节点间的链接关系，使其按相反的顺序排列。这里是一个简单的Python伪代码示例：

# 定义链表节点结构
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None  # 初始化前驱节点为空
    curr = head  # 初始化当前节点为头结点
    
    # 遍历链表，每次迭代将curr的next指向前一个节点
    while curr is not None:
        temp = curr.next  # 保存下一个节点
        curr.next = prev  # 将curr指向prev
        prev = curr      # 移动prev到curr
        curr = temp     # 移动curr到temp

    # 返回新的头结点，即原来的尾节点
    return prev

这个算法遍历整个链表一次，然后通过交换每个节点的`next`指针，实现了链表的反转。

相关问题

试写一算法，对单链表实现就地逆置c++

在C++中，对单链表进行就地逆置可以通过迭代的方式实现，以下是一个简单的算法描述：

1. 初始化三个指针，分别为`prev`（指向已逆置部分的最后一个节点），`curr`（当前节点）和`next`（下一个节点）。最初，`prev`为空，`curr`指向链表的头节点。
2. 遍历链表，对每个节点进行操作：
- 在处理当前节点`curr`之前，保存它的下一个节点`next`（使用`next = curr->next`）。
- 将当前节点的指针域反向指向前一个节点`prev`（执行`curr->next = prev`）。
- 移动指针到下一节点`curr`（`curr = next`）。
- 将`prev`移动到下一个节点，以便于下次迭代时使用（`prev = next`）。
3. 当`curr`为空时，表示已经遍历完链表，此时`prev`指向新链表的头节点。
4. 更新原链表的头指针，使其指向新的头节点`prev`。

下面是对应的C++代码示例：

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 函数实现单链表就地逆置
void reverseLinkedList(ListNode*& head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = nullptr;

    while (curr != nullptr) {
        next = curr->next;  // 保存下一个节点
        curr->next = prev;  // 反转当前节点的指针域
        prev = curr;        // 移动prev到当前节点
        curr = next;        // 移动curr到下一个节点
    }
    head = prev;  // 更新头指针为新的头节点
}

// 用于打印链表的辅助函数
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

// 主函数，用于测试链表逆置功能
int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    std::cout << "Original list: ";
    printList(head);

    reverseLinkedList(head);

    std::cout << "Reversed list: ";
    printList(head);

    // 清理链表内存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

设计一个算法对单链表实现就地逆置。

要设计一个算法来就地逆置单链表，可以采用迭代或递归的方式。这里我们使用迭代的方法，思路是创建一个新的头节点，然后遍历原始链表，每次取出一个节点并将其添加到新链表的头部。

**迭代法实现**[^1]:

def reverse_list(head):
    prev = None
    current = head

    while current:
        next_temp = current.next  # 保存当前节点的下一个节点
        current.next = prev      # 将当前节点的next指向前一个节点
        prev = current            # 更新prev指向当前节点
        current = next_temp       # 移动current到下一个未反转的节点

    if prev is not None:  # 如果不是空链表，则新头节点是原来的尾节点
        head = prev
    return head

这个算法通过改变节点之间的连接关系实现了链表的逆置，不涉及额外的空间复杂度。