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

设计一个算法来反转单向链表，可以在一次遍历过程中完成，这种方法称为迭代法，步骤如下：

1. 初始化三个指针：当前节点current、前一个节点prev和下一个节点next，初始时prev设为null，current设为头节点。

2. 遍历链表：
- 每次移动到下一个节点，即next = current.next；
- 将当前节点的指向改为前一个节点，即current.next = prev；
- 更新前一个节点和当前节点的位置，prev = current，current = next。

3. 当next变为null时，说明已经到达链表尾部，此时prev就是新的头节点，因为我们在遍历过程中改变了每个节点的指向使其倒序。

4. 返回新的头节点prev作为结果。

以下是伪代码表示：

def reverseList(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

相关问题

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

可以使用三个指针，分别指向当前结点、前一个结点和后一个结点。遍历链表时，将当前结点的链接方向指向前一个结点，然后将三个指针向后移动一个结点，直到当前结点为空。最后将原链表的头结点指向原链表的尾结点，返回新的头结点即可。这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

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

可以使用三个指针来实现链表的反转，分别为当前节点指针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;
}