链表反转（C++）_链表反转c++代码

思路图

这是在刷 LeetCode 看到的一个方法，我觉得特别简单好记，不管单链表还是双链表上来p1、p2、p3 直接反转。

代码实现

单链表反转

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)
{
	if (head == nullptr || head->right == nullptr)
		return head;
	ListNode* p1 = head;        //原表
	ListNode* p2 = head->next;     
	ListNode* p3 = nullptr;         
	while (p2)                 //第1~4回
	{
		p3 = p2->next;
		p2->right = p1;
		p1 = p2;
		p2 = p3;
	}
	head->next= nullptr;       //第5回
	head = p1;                 //第6回
	return head;
}
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
27

双链表反转

struct ListNode {
	int val;
	ListNode *left;
	ListNode *right;
	ListNode() : val(0), left(nullptr), right(nullptr) {}
	ListNode(int x) : val(x), left(nullptr),right(nullptr) {}
	ListNode(int x, ListNode *left,ListNode *right) : val(x), left(left),right(right) {}
};

//双链表反转，思路一样，多加了两行代码
ListNode* reverseList(ListNode* head)
{
	if (head == nullptr || head->right == nullptr)
		return head;
	ListNode* p1 = head;           //原表
	ListNode* p2 = head->right;
	ListNode* p3 = nullptr;
	while (p2)                     //第1~4回
	{
		p3 = p2->right;
		p2->right = p1; 
		p2->left = p3;  //新增1：p2左指针反转
		p1->left = p2;  //新增2：p1左指针反转
		p1 = p2;
		p2 = p3;
	}
	head->right = nullptr;        //第5回
	head = p1;                    //第6回
	return head;
}
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
27
28
29
30