设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转。

算法步骤如下：

1. 定义三个指针：p、q、r，分别指向当前结点、前一个结点和后一个结点。

2. 初始化：p指向链表的头结点，q指向NULL。

3. 遍历链表，每次将p的next指针指向q，然后将q、p、r三个指针向后移动一个结点。

4. 当p指向NULL时，链表已经逆转完成。

5. 最后将链表的头结点指向q，完成链表的就地逆转。

代码实现如下：

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

相关问题

设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转

可以使用三个指针prev、curr、next，分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。遍历单链表，将当前结点的next指针指向prev，然后依次向后移动三个指针，直到遍历完整个单链表。最后将原来的头结点指向原来的尾结点，即可完成单链表的就地逆转。

具体实现如下：

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

其中，head为原来的头结点，prev、curr、next分别为三个指针，初始时prev为nullptr，curr为头结点，next为头结点的下一个结点。在遍历单链表的过程中，将当前结点的next指针指向prev，然后依次向后移动三个指针。最后将原来的头结点指向原来的尾结点，即curr，完成单链表的就地逆转。

设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转的主函数

实现单链表就地逆转的算法可以采用三个指针来实现，依次将每个节点的 next 指针反转指向前一个节点即可。

具体实现如下：

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

在这个函数中，我们首先检查链表是否为空或只有一个节点，如果是，则直接返回。否则，我们定义三个指针 prev、curr 和 next，分别表示当前节点的前一个、当前和后一个节点。我们不断地循环遍历链表，将 curr 的 next 指针指向 prev，然后将 prev、curr、next 分别向后移动一个节点。当遍历到最后一个节点时，我们需要将 curr 的 next 指针指向 prev，同时将 head 的 next 指针指向空节点，最后将 head 指向 curr，就完成了链表的就地逆转。