C++ 单链表的值逆置

可以使用迭代或递归两种方法实现单链表的值逆置。

迭代方法：

1. 定义三个指针：p, q, r，分别指向当前节点、前一个节点和后一个节点。
2. 遍历链表，每次将当前节点 p 的 next 指针指向前一个节点 q，然后将 q、p、r 向后移动一个节点。
3. 当 p 指向 NULL 时，说明已经遍历到链表末尾，此时 q 指向原链表的最后一个节点，即为逆置后链表的头节点。

代码如下：

void reverseList(ListNode* head) {
    ListNode *p = head, *q = nullptr, *r = nullptr;
    while (p != nullptr) {
        r = p->next;
        p->next = q;
        q = p;
        p = r;
    }
    head = q;
}

递归方法：

1. 递归到链表末尾，返回末尾节点。
2. 在递归回溯的过程中，将当前节点的 next 指针指向前一个节点。
3. 递归结束后，原链表的最后一个节点变成逆置后链表的头节点。

代码如下：

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* p = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return p;
}