ch11.2-7 链表逆置

### 链表逆置的实现方法

链表是一种常见的线性数据结构，其特点是节点之间通过指针链接。对于单向链表而言，每个节点包含两部分：存储数据的部分和指向下一个节点的指针。

#### 单链表逆置算法描述

为了逆转一个单链表，可以采用迭代的方法来逐个反转相邻两个节点之间的连接方向。具体来说：

- 初始化三个指针变量 `prev`、`current` 和 `next` 分别用于保存前驱节点、当前处理中的节点以及后续待处理的第一个节点。
- 开始时令 `prev=nullptr`, 表示新的头结点之前没有任何元素；让 `current=head` 指向原始链表头部；
- 进入循环体，在每次迭代过程中先暂存下一轮要访问的位置即 `next=current->next`;
- 接着修改当前节点的 next 字段使其指向前一位置 (`current->next=prev`);
- 更新 prev 和 current 的值分别为原来的 current 和 next;
- 当遍历结束条件满足（即到达原链表末端），则把 head 设置成最后一个非空节点也就是新形成的反向列表的新起点[^1]。

下面是 C++ 版本的具体代码实现方式:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head, *nxt;

    while (curr != nullptr){
        nxt = curr->next;       // Store reference to the rest of list.
        curr->next = prev;      // Reverse link direction at this node.
        prev = curr;            // Move forward one step in original order.
        curr = nxt;             // Continue with remaining nodes.
    }

    return prev;                // New first element is last non-null 'prev'.
}

此函数接收一个指向单链表首元节点的指针作为参数，并返回一个新的指针指向经过翻转后的链表起始处。该过程的时间复杂度为 O(n)，其中 n 是输入序列长度，因为只需一次完整的扫描即可完成整个操作。