当前位置:网站首页>C language to quickly solve the reverse linked list
C language to quickly solve the reverse linked list
2022-07-04 23:15:00 【I'm not Xiao Haiwa~~~~】
Reverse a linked list
Title Description :
Given the head node of a single linked list pHead( The header node has a value , For example, in the figure below , its val yes 1), The length is n, After reversing the linked list , Return the header of the new linked list .
Data range : 0≤n≤1000
requirement : Spatial complexity O(1) , Time complexity O(n)O(n)
For example, when entering a linked list {1,2,3} when , After reversal , The original linked list becomes {3,2,1}, So the corresponding output is {3,2,1}.
The above conversion process is shown in the figure below :
This paper introduces two methods :
(1) Reverse in place
(2) Double linked list method
( I think the two methods are similar …)
/*struct ListNode { int val; struct ListNode *next; }; */
// use c Language implementation
struct ListNode* ReverseList(struct ListNode* pHead ) {
struct ListNode *pre=NULL;//pre The pointer points to the last node of the inverted linked list , There was no reversal at first , So the point to null
struct ListNode *cur=pHead;//cur The pointer points to the first node of the linked list to be reversed , Wait for the first node to reverse , So the point to head
struct ListNode *nex=NULL;// Used to save broken chain nodes , That is, the pointer points to the second node of the linked list to be reversed
while(cur){
nex=cur->next;
cur->next=pre;// Realize the chain breaking operation
pre=cur;// Inverted node
cur=nex;// Point to the previously broken node
}
return pre;
}
// Double linked list implementation
struct ListNode* ReverseList(struct ListNode* pHead ) {
struct ListNode *newHead=NULL;
while(pHead!=NULL){
struct ListNode *temp=pHead->next; // Save the broken chain node
pHead->next=newHead;// Hang the new linked list after the visited original linked list node
newHead=pHead;
pHead=temp;
}
return newHead;
}
notes : You can also use stack to realize this problem , The first in and last out output just realizes the inversion
original text :https://blog.csdn.net/qq_46027119/article/details/124182305
边栏推荐
- Principle of lazy loading of pictures
- Mysql database backup and recovery -- mysqldump command
- How can enterprises cross the digital divide? In cloud native 2.0
- Redis introduction complete tutorial: Collection details
- 【剑指Offer】6-10题
- Redis入门完整教程:API的理解和使用
- Qt个人学习总结
- P2181 对角线和P1030 [NOIP2001 普及组] 求先序排列
- VIM editor knowledge summary
- ScriptableObject
猜你喜欢
Analysis of the self increasing and self decreasing of C language function parameters
Qualcomm WLAN framework learning (30) -- components supporting dual sta
phpcms付费阅读功能支付宝支付
Redis入门完整教程:慢查询分析
壁仞科技研究院前沿技术文章精选
CTF竞赛题解之stm32逆向入门
Redis入門完整教程:Pipeline
The initial trial is the cross device model upgrade version of Ruijie switch (taking rg-s2952g-e as an example)
【剑指offer】1-5题
cout/cerr/clog的区别
随机推荐
【taichi】用最少的修改将太极的pbf2d(基于位置的流体模拟)改为pbf3d
ECS settings SSH key login
Observable time series data downsampling practice in Prometheus
P2181 diagonal and p1030 [noip2001 popularization group] arrange in order
MariaDB的Galera集群-双主双活安装设置
[odx Studio Edit pdx] - 0.2 - Comment comparer deux fichiers pdx / odx
Redis入门完整教程:Redis Shell
Redis入门完整教程:慢查询分析
How to choose a securities company? Is it safe to open an account on your mobile phone
Redis getting started complete tutorial: Geo
Tweenmax emoticon button JS special effect
云服务器设置ssh密钥登录
A complete tutorial for getting started with redis: Pipeline
Redis入门完整教程:Pipeline
Notepad++--编辑的技巧
Redis入门完整教程:列表讲解
Sword finger offer 68 - I. nearest common ancestor of binary search tree
Redis入门完整教程:初识Redis
金融市场,资产管理与投资基金
ScriptableObject