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;
}

LeetCode 热题 100_反转链表(23_206)原题链接
 大佬画的递归图解链接（感觉不错）
欢迎大家和我沟通交流(✿◠‿◠)

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