6-146 逆置链表

在计算机编程中，6-146 通常指的是 LeetCode 上的一个题目，名为 "Reverse Linked List"（反转链表）。这个题目要求你设计一个函数，输入一个单链表，将其节点的顺序反转，即原来的头节点变成尾节点，依次类推。

具体实现步骤如下：

1. 定义一个辅助指针 `prev` 和 `current`，初始时都指向 `None`，分别作为上一个节点和当前节点。
2. 遍历链表，从头节点开始：
- 将 `current` 的下一个节点保存到临时变量中，以防止丢失原链表的连接。
- 将 `current` 的指针更新为 `prev`，完成一次反转操作。
- 将 `prev` 指针移动到 `current` 的位置，继续处理下一次反转。
3. 当遍历到最后一个节点时，将最后一个节点的下一个节点设置为头节点（因为 `prev` 在遍历结束后指向的就是原头节点）。
4. 返回新头节点，即原链表的尾节点。

相关问题：
1. 在链表反转过程中，为什么要使用两个指针？
2. 如果链表为空，应该如何处理？
3. 这个问题的递归解法是什么样子的？

相关问题

6-146 逆置链表代码

在编程中，6-146 通常指的是LeetCode上的一个题目，要求你实现一个函数来逆置单链表。这里是一个简单的Python代码示例，使用迭代的方式来解决这个问题：

# 定义链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr:
        # 保存当前节点的下一个节点
        next_temp = curr.next
        # 将当前节点的next指向前一个节点
        curr.next = prev
        # 更新前一个节点和当前节点
        prev = curr
        curr = next_temp
    return prev  # 返回新的头节点，原头节点变成尾节点

这段代码的工作原理是，遍历链表时，每次都将当前节点的`next`指向前一个节点，然后移动`prev`和`curr`到下一对节点，直到遍历完整个链表。最后返回`prev`作为新的头节点。

如果你需要了解更深入的代码实现细节、算法分析或者其他编程语言的版本，或者对这个题目有任何疑问，请告诉我，我会很乐意帮助解答。

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 是输入序列长度，因为只需一次完整的扫描即可完成整个操作。