设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链 表，将链表中所有结点的链接方向逆转，如图2.2所示。要求逆转结果链 表的表头指针 h 指向原链表的最后一个结点。

要设计一个算法来逆转单链表的方向，可以采用迭代的方式，步骤如下：

1. 初始化两个指针，`prev` 为 `NULL`（表示空），`cur` 初始设置为链表的头节点 `h`。

2. 当 `cur` 不为 `NULL` 时，执行以下操作：

   a. 将当前节点 `cur` 的 `next` 指针指向 `prev`，完成逆转操作。
   b. 更新指针位置：`prev` 赋值给 `cur`，`cur` 赋值给 `cur.next`。

3. 循环结束后，`prev` 就会成为新的表头，因为最后 `cur` 会指向原来的尾节点，而 `prev` 最终指向的就是新的第一个节点。

这里是具体的伪代码实现[^1]：

reverseLinkedList(h):
    prev = NULL
    cur = h

    while cur != NULL:
        cur.next = prev
        prev = cur
        cur = cur.next

    return prev  # 返回新表头，即原表尾

现在，链表的方向已经被逆转，新的表头 `prev` 指向的是原链表的最后一个结点。

相关问题

设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链 表，将链表中所有结点的链接方向逆转，如图2.2所示。要求逆转结果链 表的表头指针 h 指向原链表的最后一个结点

要实现这个功能，你可以按照以下步骤设计算法：

1. 定义两个指针，`prev` 和 `current`，初始化时，`prev` 设置为 `NULL`，`current` 设置为链表的头节点 `h`。

2. 创建一个新的临时指针 `next`，用于存储 `current` 的下一个节点。

3. 开始遍历链表：

   while current is not None:  # 当 current 不为空时
       temp = current.next  # 备份 current 的下一个节点
       current.next = prev  # 更新 current 的下一个节点为 prev（即将其反向）
       prev = current  # 移动 prev 到 current
       current = temp  # 移动 current 到下一个节点

4. 链表遍历结束后，链表的头节点 `h` 就变成了原链表的尾节点，所以最后更新 `head` 为 `prev`。

这是基于伪代码的Python实现，但请注意，这里的语法是Python，如果你是在C/C++环境中，会有所不同。以下是C++版本的代码实现：

void reverseList(Node* &h) {
    Node* prev = nullptr;
    Node* current = h;

    // 遍历链表
    while (current != nullptr) {
        Node* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }

    // 更新头节点为原链表尾节点
    h = prev;
}

其中，`Node*` 是链表节点的定义，`&h` 表示传入的链表头指针的地址。

设有一个表头指针为HEAD的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有节点的链接方向逆转。要求逆转结果中链表的表头指针 HEAD指向原链表的最后一个节点。

要实现这个操作，可以采用迭代的方式。以下是步骤：

1. **初始化两个指针**：创建两个指针`prev`和`current`，分别初始化为`NULL`和`HEAD`。
- `prev`用于保存当前节点的前驱节点，初始时没有前驱。
- `current`用于遍历链表。

2. **遍历链表**：当`current`不为`NULL`时，进入循环。
- 记录当前节点的下一个节点：`nextNode = current->next`。
- 更新当前节点的指向下一位：`current->next = prev`。
- 移动指针到下一个节点：`prev = current`。
- `current`向前移动：`current = nextNode`。

3. **处理特殊情况**：在遍历结束时，即`current`变为`NULL`，将`prev`设置为新的头结点，因为经过上面的操作，`prev`已经指向了原链表的最后一个节点。

4. **返回新表头**：最后返回`prev`作为逆转后的链表的新头结点。

算法伪代码如下：

function reverseList(HEAD):
    prev = NULL
    current = HEAD

    while current is not NULL:
        nextNode = current.next
        current.next = prev
        prev = current
        current = nextNode

    HEAD = prev  # 新的头结点是原来的尾结点
    return HEAD