前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给你单链表的头节点 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. 定义链表结构的结构体struct
2. 三个struct类型的指针，分别是pre，cur，tmp。

2. 本题思路分析：

1. 主要就是通过三个指针不断循环，让节点指针从后向前翻转。

3. 算法实现

• 代码：

#include
#include
using namespace std;
struct ListNode{
	int val;
	ListNode* next;
	ListNode(): val(0),next(nullptr){}
	ListNode(int x): val(x),next(nullptr){}
	ListNode(int x,ListNode* next):val(x),next(next){}
};
ListNode* reverseList(ListNode* head) {
	ListNode* pre = nullptr;
	ListNode* cur = head;
	ListNode* tmp = nullptr;
	while(cur != nullptr){
		//将指针指向cur的下一个位置 
		tmp = cur -> next; 
		//反转指针 
		cur -> next = pre;
		//将指针往后移动 
		pre = cur;
		cur = tmp;
	}
	return pre;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4. 算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

5. 算法坑点

1. tmp初始化应该放到训话之中，否则会出现最后一次循环，cur已经指向nullptr了，还要cur -> next = pre的指令，就会报错。