编写算法，实现带头节点单链表的就地逆置，即利用原带头节点单链表的结点空间把元素序列逆置

算法步骤如下：

1. 定义三个指针：p、q、r，分别指向链表的头结点、第一个结点和第二个结点；
2. 将 q 指向的结点的 next 指针指向 p，即将第一个结点反向连接到头结点之后；
3. 将 p、q、r 依次向后移动一个位置，即将 q 移动到第二个结点，将 r 移动到第三个结点；
4. 循环执行步骤2-3，直到 r 指向空节点，即完成链表的就地逆置。

算法实现如下：

void reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* p = head->next;
    Node* q = p->next;
    Node* r = nullptr;
    while (q != nullptr) {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    head->next->next = nullptr;
    head->next = p;
}

其中，head 为头结点，Node 为链表结点类型。需要注意的是，在完成链表逆置后，需要将原来的尾结点的 next 指针置为空，否则会出现环形链表的问题。

相关问题

编写算法实现带头结点单链表的就地逆置，即利用原带头节点单链表的节点空间把元素序列 a0,a1…, an-1 逆置为an-1,…,a1,a0。

思路：

- 首先判断链表是否为空，或者链表只有一个节点，则不需要逆置。
- 定义三个指针：prev、cur和next，分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
- 在遍历链表的过程中，依次将当前节点的 next 指针指向 prev，然后依次向后移动 prev、cur 和 next 指针。
- 遍历完成后，将原头结点的 next 指针指向新的表头节点。

代码实现：

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

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    prev, cur, next = None, head.next, head.next.next
    while next:
        cur.next = prev
        prev, cur, next = cur, next, next.next
    cur.next = prev
    head.next = cur
    return head

其中，head 为带头结点的单链表头结点，返回值为逆置后的头结点。

P39 编写算法实现带头结点单链表的就地逆置，即利用原带头节点单链表的节点空间把元素序列 a0,a1…, an-1 逆置为an-1,…,a1,a0。

算法实现如下：

1. 定义三个指针：pre、cur、suc，分别指向当前节点的前驱、当前节点、当前节点的后继。
2. 将 cur 指向头结点的下一个节点，pre 指向头结点，suc 指向 cur 的后继。
3. 遍历链表，对于每个节点，将其指向其前驱节点，然后依次更新 pre、cur、suc 指针。
4. 遍历结束后，将头结点的下一个节点指向 pre，完成链表的就地逆置。

代码实现如下：

void reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode* pre = head;
    ListNode* cur = head->next;
    ListNode* suc = cur->next;
    pre->next = nullptr;
    while (cur != nullptr) {
        cur->next = pre;
        pre = cur;
        cur = suc;
        if (suc != nullptr) {
            suc = suc->next;
        }
    }
    head->next = pre;
}