当前位置:网站首页>LeetCode206. Reverse linked list [double pointer and recursion]
LeetCode206. Reverse linked list [double pointer and recursion]
2022-07-07 22:49:00 【Qingshan's green shirt】
LeetCode206. Reverse a linked list
List of articles
1. subject
2. Ideas
1. My initial idea was to move the last node forward in turn , Later, I found two difficulties . One is that the one-way linked list cannot access the precursor nodes of the known nodes , Made some mistakes . such as :
(1)LinkNode*q; q->next = p; //q It doesn't point to p The precursor of
(2)LinkNode *q = dummyHead; q->next = p; // This will become dummyHead Of next Turn into p The linked list is wrongly arranged !
Second, if you need to access the precursor node , Every time I need to traverse , Time complexity is too high . Sum up , I gave up the idea .
2. Double pointer application . Set one front node and one rear node to move backward in sequence . Make the pointer of the following node point to the node in front of it .
3. recursive .
Let's implement it separately .
3. Code implementation
(1) Double pointer application
The basic idea of double pointer :
1. My initial idea is to count the length of the linked list , The special judgment length is 0/1 The situation of , Finally, use double pointers . This is a little complicated
2. Remember to use tmp After the node is saved, the node behind the pointer , Or you lose it
The main idea is the figure above :(1) Save node (2) Pointer reversal (3) Pointer backward
First post my initial code , Very complicated , There are many redundant steps …
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* dummyHead = new ListNode(1);// Sentinel node Consider that the header node is empty
if(head!= NULL) dummyHead->next = head;
ListNode* p = dummyHead;
int size = 0;// initialization !
while(p->next != NULL)
{
p = p->next;
size++;// Chain length
}
// It is specially judged that the empty linked list and length are 1 The situation of
if(size == 0) return nullptr;
else if(size == 1) return head;
else{
ListNode *m = dummyHead->next;
ListNode *n = dummyHead->next->next;
ListNode *tmp;
while(n != NULL)
{
// Save node
tmp = n->next;
// reverse
n->next = m;
m = n;
// Move backward
n = tmp;
}
dummyHead->next->next = nullptr;// This sentence must have a meaning
delete dummyHead;
return m;
}
}
};
Compared with the big guy's code, there are two biggest shortcomings :
1. There is no need to use sentinel nodes , Too much , And easy to lose
dummyHead->next->next = nullptr;
This step .
2. Recently, I have developed the awareness of special judgment , The empty linked list and nodes will be 1 Think about the linked list , Very happy . But special judgment is not necessary , Can be more streamlined !
The streamlined code :
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tmp;
ListNode* m = NULL;
ListNode* n = head;
while(n != NULL)
{
// Save node
tmp = n->next;
// reverse
n->next = m;
// Move backward
m = n;
n = tmp;
}// There is no need to make a special judgment on the head node , The first step is to set NULL 了
return m;
}
};
(2) Recursive method
The same idea as double pointer
ListNode* reverse(ListNode*m,ListNode* n){
if(n == NULL) return m;// Recursive export
// Storage point
ListNode* tmp = n->next;
// In exchange for
n->next = m;
// Move backward Here I stuck for a while But it's actually the same as the double pointer idea
//m = n;
//n = tmp;
return reverse(n,tmp);
}
ListNode* reverseList(ListNode* head) {
// Is the initialization of double pointers
//ListNode* m = NULL; ListNode* n = head;
return reverse(NULL,head);
}
边栏推荐
- Debezium series: support the use of variables in the Kill Command
- 7-18 simple simulation of banking business queue
- Nx10.0 installation tutorial
- Matplotlib quick start
- [interview arrangement] 0211 game engine server
- Debezium series: set role statement supporting mysql8
- 「开源摘星计划」Loki实现Harbor日志的高效管理
- OpenGL jobs - shaders
- 23. Merge K ascending linked lists -c language
- The PHP source code of the new website + remove authorization / support burning goose instead of pumping
猜你喜欢
[azure microservice service fabric] how to transfer seed nodes in the service fabric cluster
PKPM 2020 software installation package download and installation tutorial
. Net automapper use
How pyGame rotates pictures
Robot autonomous exploration series papers environment code
Form组件常用校验规则-2(持续更新中~)
Dayu200 experience officer MPPT photovoltaic power generation project dayu200, hi3861, Huawei cloud iotda
微服務遠程Debug,Nocalhost + Rainbond微服務開發第二彈
Ueeditor custom display insert code
Overseas agent recommendation
随机推荐
Yarn开启ACL用户认证之后无法查看Yarn历史任务日志解决办法
Revit secondary development - modify wall thickness
「开源摘星计划」Loki实现Harbor日志的高效管理
Px4 autonomous flight
Variables and constants
苹果在iOS 16中通过'虚拟卡'安全功能进一步进军金融领域
De la famille debezium: SET ROLE statements supportant mysql8
Blender exchange group, welcome to the water group ~
Dbsync adds support for mongodb and ES
Revit secondary development - collision detection
Take full control! Create a "leading cockpit" for smart city construction
100million single men and women "online dating", supporting 13billion IPOs
php 记录完整对接腾讯云直播以及im直播群聊 所遇到的坑
OpenGL homework - Hello, triangle
[environment] pycharm sets the tool to convert QRC into py file
Pdf document signature Guide
Cannot find module 'xxx' or its corresponding type declaration
Revit secondary development - shielding warning prompt window
Quick sort (diagram +c code)
Cataloger integrates lidar and IMU for 2D mapping