设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

算法步骤如下：

1. 定义三个指针：pre、cur、next，分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。

2. 将 cur 指向链表的头结点，pre 和 next 分别指向 NULL。

3. 遍历链表，每次将 cur 的 next 指向 pre，然后将 pre、cur、next 向后移动一个结点，直到 cur 指向 NULL。

4. 最后将链表的头结点指向 pre，完成链表的逆转。

算法实现如下：

void reverseList(ListNode* &head) {
    ListNode *pre = NULL, *cur = head, *next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head = pre;
}

其中，head 是指向链表头结点的指针，& 表示传递指针的引用，即可以修改指针指向的内容。ListNode 是链表结点的定义，包含一个指向下一个结点的指针 next。

相关问题

设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的 存储空间

这个问题可以用迭代的方式来解决，具体步骤如下：

1. 定义三个指针：prev, curr, next，分别表示当前结点的前驱结点、当前结点和后继结点。

2. 初始化 prev 为 NULL，curr 为链表头结点。

3. 遍历整个链表，每次循环将 curr 的 next 指针指向 prev，然后依次将 prev、curr、next 指针向后移动一个结点，直到 curr 指向最后一个结点。

4. 将链表的头指针指向反转后的最后一个结点，即原链表的尾结点。

以下是具体实现的伪代码：

reverseLinkedList(head):
    prev = NULL
    curr = head
    while curr is not NULL:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    head = prev
    return head

其中，head 表示链表头指针，curr.next 表示当前结点的后继指针，prev 表示当前结点的前驱指针，next 表示当前结点的下一个结点。

设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间

可以使用三个指针来实现链表的反转，分别为当前节点指针cur、前驱节点指针pre和后继节点指针next。具体步骤如下：

1. 将当前节点指针cur指向链表的头节点。
2. 遍历链表，当cur指针不为空时，执行以下操作：
a. 将后继节点指针next指向cur的下一个节点。
b. 将cur的下一个节点指向前驱节点pre。
c. 将前驱节点指针pre指向当前节点cur。
d. 将当前节点指针cur指向后继节点指针next。
3. 遍历结束后，将链表的头节点指向前驱节点pre，即可完成链表的反转。

代码实现如下：

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