单链表反序实现

这个算法题有两种实现方式，一种是迭代，就是循环，还有一种是递归实现

迭代实现

迭代实现原理上是在一个循环如for中依次将一个节点的方向改变达到原地反序的实现

迭代法的核心是使用三个指针​（prev, curr, next）逐个节点调整指针方向，逐步将链表反转。具体步骤如下：

1. ​初始化指针：prev指向空，curr指向头节点。
2. ​遍历链表：每次循环将curr->next指向prev，然后更新prev和curr的指向。
3. ​终止条件：当curr遍历到链表尾部（curr == nullptr）时停止。

struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;  // 前驱指针，初始为空ListNode* curr = head;     // 当前指针，从头节点开始遍历while (curr != nullptr) {ListNode* next = curr->next; // 保存下一个节点curr->next = prev;           // 反转当前节点的指针方向prev = curr;                 // prev指针前移，记录当前改的节点防止断链curr = next;                 // curr指针前移}return prev; // 最终prev指向新头节点（原链表尾节点）
}

以链表 1 → 2 → 3 → 4 → 5 为例，逐步演示反转过程：

步骤	操作前状态	操作后状态	关键代码
1	prev=null, curr=1	1→null, prev=1, curr=2	curr->next = prev
2	prev=1, curr=2	2→1, prev=2, curr=3	curr->next = prev
3	prev=2, curr=3	3→2, prev=3, curr=4	curr->next = prev
4	prev=3, curr=4	4→3, prev=4, curr=5	curr->next = prev
5	prev=4, curr=5	5→4, prev=5, curr=nullptr	curr->next = prev

最终，prev指向节点5（新头节点），链表变为 5 → 4 → 3 → 2 → 1。

递归实现

递归的核心思想是将链表分解为头节点和剩余子链表两部分。递归反转子链表后，通过调整指针方向将头节点连接到反转后的子链表尾部，最终实现整个链表的反转

​关键步骤：

1. ​终止条件：若链表为空（head == nullptr）或仅有一个节点（`head->next == nullptr``），直接返回头节点（无需反转）。
2. ​递归反转子链表：递归调用处理head->next后的子链表，返回反转后的新头节点rest。
3. ​调整指针：将当前节点的下一个节点（head->next）的next指向当前节点，形成反向连接，并将当前节点的next置空以避免循环。

struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};ListNode* reverseList(ListNode* head) {// 终止条件：空链表或单节点链表无需反转if (head == nullptr || head->next == nullptr) {return head;}// 递归反转子链表，得到新头节点restListNode* rest = reverseList(head->next);// 调整指针方向head->next->next = head;  // 子链表尾节点指向当前头节点head->next = nullptr;     // 断开原链表的正向连接// 返回反转后的新头节点（即原链表的尾节点）return rest;
}

递归是有两个指针，一个head，一个rest记录新节点，递归分为递阶段和归阶段，在满足if条件的时候比如链表是12345，head会先一直走到5的位置，rest也会在5这个位置记录下来返回作为新的头节点 ，这时候head的next指针指向nullptr，不满足if条件，就不会再进行递了，再开始归执行下面的指针方向转换，每次执行完归一层，如5节点执行完会走到4。

注意：递归每次创建调用都会创建一套自己的新的变量，比如这个程序每次都是传入head的next作为参数构造，每次head都是一个全新的指针，他们的参数和作用域不同，和原来的head不同，他们只是名字相同。