1、用递归算法反转一个单链表C++

单链表反转是一个经典问题，可以用迭代和递归两种方式来实现。 1. 迭代法 迭代法的思路是，从头节点开始，依次将每个节点的指针反转，直至将整个链表反转。具体步骤如下： - 定义三个指针：prev、curr、next，分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。 - 初始化prev为nullptr，curr为头节点。 - 遍历链表，重复以下操作： - 将next指针指向curr的下一个节点。 - 将curr的next指针指向prev。 - 将prev指向curr。 - 将curr指向next。 - 遍历结束后，将头节点指向prev。 下面是迭代法的代码实现： ```c++ ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } ``` 2. 递归法 递归法的思路是，将整个链表分为两部分：第一个节点和剩余节点。假设剩余节点已经被反转，现在要将第一个节点加入到反转后的链表中。 具体步骤如下： - 如果链表为空或只有一个节点，直接返回该链表。 - 递归反转剩余节点，得到新的头节点newHead。 - 将第一个节点的next指针指向空。 - 将newHead的尾节点与第一个节点相连。 - 返回newHead。 下面是递归法的代码实现： ```c++ ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; } ```

<think>好的，我现在需要解决一个关于单链表反转的问题，要求是原地反转，不使用数组或容器，也不开辟新的节点空间。编程语言可以是C/C++或Python，数据结构是单链表。首先，我得回忆一下链表的基本操作和反转算法的常见方法。 首先，单链表的结构每个节点包含数据和指向下一个节点的指针。反转链表的关键在于改变指针的方向，使得原本指向下一个节点的指针指向前一个节点。这样整个链表的顺序就反转了。但是如何在不使用额外空间的情况下做到这一点呢？ 我记得常见的原地反转方法是使用迭代法或者递归法。不过递归可能会使用栈空间，虽然不是显式的数组或容器，但可能不符合题目中“不开辟新节点空间”的要求，因为递归调用会占用栈空间。因此，迭代法可能更合适。 迭代法的思路是维护三个指针：前驱节点（prev）、当前节点（current）和下一个节点（next）。初始时，prev设为null，current指向头节点。然后遍历链表，每次将current的next指向prev，然后prev和current依次向后移动，直到current为null，此时prev就是新的头节点。 比如，假设链表是1->2->3->4->null，反转过程应该是这样的： 1. prev=null, current=1，保存next=2 2. current->next指向prev（即null），prev移动到current的位置（1），current移动到next的位置（2） 3. 重复这个过程，直到current为null，此时prev就是新的头节点4，链表变为4->3->2->1->null 那具体实现的话，需要处理每个节点的指针指向。在C语言中，单链表的结构体可能定义为： struct ListNode { int val; struct ListNode *next; }; 反转函数需要接收头节点，并返回新的头节点。比如函数原型可能是struct ListNode* reverseList(struct ListNode* head)。 现在需要考虑边界情况，比如链表为空或者只有一个节点的情况，这时候直接返回头节点即可。对于多个节点的情况，按照上述步骤处理。 Python的实现可能更简单，因为不需要处理指针的细节，但同样要遵循同样的逻辑。不过题目中允许使用Python，所以可以用类似的迭代方法。 那现在如何验证这个算法的正确性呢？比如测试用例： 输入：1->2->3->4 输出：4->3->2->1 或者输入空链表返回空等。 另外，有没有可能使用递归的方法？递归的话，每次递归处理子链表，但需要确保不创建新节点。递归的终止条件是当前节点或下一个节点为空。然后递归到最后一个节点，作为新的头节点，然后逐层返回，修改指针方向。不过递归的空间复杂度是O(n)，因为需要递归栈，这可能不符合题目的要求，所以题目可能更期望迭代的方法。 现在，我需要确保代码中不会使用任何数组或容器，比如Python中的列表，或者C中的数组来存储节点。所以必须完全通过指针操作来完成。 综上，正确的做法应该是使用迭代法，通过三个指针的移动来逐个反转节点的指向。这样空间复杂度是O(1)，符合要求。 现在具体编写代码的话，以C语言为例： struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *current = head; struct ListNode *next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转指针 prev = current; // 移动prev current = next; // 移动current } return prev; // prev现在是新的头节点 } 这个函数是否正确？比如当链表为空时，返回NULL；当链表只有一个节点时，循环不会执行，直接返回prev即原head。是的。 在Python中，节点的定义可能是这样的： class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 对应的反转函数： def reverseList(head: ListNode) -> ListNode: prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev 这样同样正确，而且没有使用任何额外的数据结构，完全原地修改指针。 现在检查是否满足所有条件：不借助数组或容器、不开辟新节点空间。是的，只是改变现有节点的next指针指向，没有创建新节点，所以符合要求。 总结，这就是原地反转单链表的标准方法，时间复杂度O(n)，空间复杂度O(1)。</think>### 单链表原地反转实现方法 要实现原地反转单链表，只需通过调整节点指针指向即可，无需额外空间。以下是具体实现步骤： #### 算法思路 使用迭代法，维护三个指针： - `prev`：前驱节点（初始为`NULL`） - `current`：当前遍历节点（初始为头节点） - `next`：临时保存当前节点的下一个节点 每次迭代执行以下操作： 1. 保存`current->next`到`next` 2. 将`current->next`指向`prev`（反转指针） 3. `prev`和`current`依次向后移动 4. 最终`prev`成为新链表的头节点 #### C语言实现 ```c struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *current = head; struct ListNode *next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转指针指向 prev = current; // 前驱指针后移 current = next; // 当前指针后移 } return prev; // 新头节点 } ``` #### Python实现 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseList(head: ListNode) -> ListNode: prev = None current = head while current: next_node = current.next # 保存下一个节点 current.next = prev # 反转指针指向 prev = current # 前驱指针后移 current = next_node # 当前指针后移 return prev # 新头节点 ``` #### 关键点分析 1. **指针操作**：通过直接修改节点指针方向实现反转，空间复杂度为$O(1)$[^3]。 2. **边界处理**：链表为空或仅有一个节点时，代码仍能正确运行。 3. **时间复杂度**：$O(n)$，遍历链表一次完成反转。 #### 示例演示 原链表：$1 \rightarrow 2 \rightarrow 3 \rightarrow \text{NULL}$ 反转过程： 1. `prev=NULL`, `current=1` → 反转后 `1→NULL`，`prev=1` 2. `current=2` → 反转后 `2→1`，`prev=2` 3. `current=3` → 反转后 `3→2`，`prev=3` 最终链表：$3 \rightarrow 2 \rightarrow 1 \rightarrow \text{NULL}$ ---