LeetCode 热题 100_反转链表(23_206_简单_C++)(单链表

LeetCode 热题 100_反转链表(23_206_简单_C++)(单链表_递归)

LeetCode 热题 100_反转链表（23_206）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（迭代）：
    - 思路二（简化方法一(迭代)代码）：
    - 思路三（递归）：
  - 代码实现
  - - 代码实现（思路一（迭代））：
    - 代码实现（思路二（简化方法一(迭代)代码））：
    - 代码实现（思路三（递归））：
    - - 思路三递归函数调用的过程：
    - 以思路三为例完成代码调试

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入输出样例：

示例 1：
请添加图片描述

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
请添加图片描述

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题解：

解题思路：

思路一（迭代）：

1、通过题目分析，实现翻转链表，这里我们可以逐个结点进行翻转。
例： 1->2->3->4->5->null
第一步:listA:1->null, listB:2->3->4->5->null, 拿出1节点，并让其指向空。

第二步：LsitA:2->1->null, listB:3->4->5->null 将2节点插入在1节点之前，注意保存3节点位置信息。

… 总结上两步：需要3个指针分别存储listA的首结点，listB的首节点,和一个需要移动的节点。

listA:5->4->3->2->1->null

以第一步->第二步为例*pre=1,*temp=2,*r=2
首先r保存后继节点3(r=3),现在temp可以移动改变指向，temp->next=pre,接下来pre=temp，pre移动到头部
此时移动完成，temp=r,准备下一次的移动。此时pre=2,*temp=3,*r=3。

2、复杂度分析：
① 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
② 空间复杂度：O(1)。

思路二（简化方法一(迭代)代码）：

1、我们可以把nullptr看作为listA的首节点，这样我们的转换过程就可以看成一个重复的循环。

2、复杂度分析：
① 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
② 空间复杂度：O(1)。

思路三（递归）：

1、递归代码讲解请看思路三代码实现下方（函数调用的过程）。
2、复杂度分析：
时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

代码实现

代码实现（思路一（迭代））：

ListNode* reverseList1(ListNode* head) {//pre是listA首节点，r代表listB的首节点，temp代表移动节点 ListNode *pre=head,*r=nullptr,*temp=nullptr;if(pre!=nullptr){      r=temp=head->next;  	pre->next=nullptr;while(r!=nullptr){r=temp->next; //暂存后继节点 temp->next=pre;  //修改next指向 pre=temp;temp=r;}}return pre;  
}

代码实现（思路二（简化方法一(迭代)代码））：

ListNode* reverseList2(ListNode* head) {//pre是listA首节点，r代表listB的首节点ListNode *pre=nullptr,*r=head; while(r!=nullptr){//temp代表移动节点 ListNode* temp=r;r=temp->next;    temp->next=pre;pre=temp;temp=r;}return pre;
}

代码实现（思路三（递归））：

ListNode* reverseList3(ListNode* head) {//递归出口,head为null或者head->next为null if (!head || !head->next) {  //①return head;          }ListNode* newHead = reverseList3(head->next);head->next->next = head;  //②head->next = nullptr;     //③return newHead;           //④
}

思路三递归函数调用的过程：

//将reverseList3(ListNode* head)函数递归过程做如下简化表示 
r(1){//①r(2){//①r(3){//①r(4){//①r(5){①返回5结点（到了递归出口） }②这里的head就是r(4)中的4，1->2->3->4<-5 ③将4结点的next指向nullptr ④返回5结点 }②这里的head就是r(3)中的3，1->2->3<-4<-5③将3结点的next指向nullptr④返回5结点}②这里的head就是r(2)中的2，1->2<-3<-4<-5③将2结点的next指向nullptr④返回5结点}②这里的head就是r(1)中的1，1<-2<-3<-4<-5③将1结点的next指向nullptr,null<-1<-2<-3<-4<-5④返回5结点
}
总结：
1、递归出口中 if (!head || !head->next)， !head是防止一开始为空，!head->next是找到最后一个结点 
2、②的目的是为了调转指针的方向
3、③的目的就是为了最后给1的next赋nullptr 
4、④的目的仅仅就是为了保存翻转后的首结点

以思路三为例完成代码调试

#include<iostream>
#include<vector>
using namespace std;struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(nullptr){};
};//创建单链表（尾插法）
ListNode* createList(vector<int> &arr){ListNode* head=nullptr;ListNode* tail=nullptr;for(const auto &val:arr){ListNode* newNode = new ListNode(val);if(head==nullptr){head=newNode;tail=newNode;}else{tail->next=newNode;tail=newNode;}}return head;
}ListNode* reverseList3(ListNode* head) {//递归出口,head为null或者head->next为null if (!head || !head->next) {  //①return head;          }ListNode* newHead = reverseList(head->next);head->next->next = head;  //②head->next = nullptr;     //③return newHead;           //④
}int main(){vector<int> arr={1,2,3,4,5};ListNode* head=createList(arr);ListNode* ans=reverseList3(head);while(ans!=nullptr){cout<<ans->val<<"->";ans=ans->next;}cout<<"null"; return 0;
}