满堂花醉三千客,一剑霜寒十四州。这篇文章主要讲述[ 链表OJ题 --C语言实现 ] 反转链表相关的知识,希望能为你提供帮助。
目录
题目描述:
代码实现:
1、方法一:
1.1思路分析:
2、方法二:
2.1思路分析
题目描述:
代码实现:1、方法一:struct ListNode* reverseList(struct ListNode* head)
if(!head) return NULL;
struct ListNode* n1,* n2,* n3;
n1=NULL;
n2=head;
n3 = n2->
next;
while(n2)
n2->
next =n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->
next;
return n1;
1.1思路分析:
我们要让原链表逆置,我们可以让箭头反过来,再把head指向尾结点即可。
因此我们可以创建3个变量n1,n2,n3;其中n1置空,用来让头结点的next指向空,让n2赋值为head,n3用来保存n2的next节点,其中n3的创建是必须的,因为当箭头逆置时,n2的next指向了n1,就无法找到原链表中n2的next节点,而且原链表中n2的next节点有且仅有n2可以找到,因此,n3的作用就是保存原链表中n2的next节点。
其中:
【[ 链表OJ题 --C语言实现 ] 反转链表】1、当原链表为空时,需要直接返回NULL;
2、n2->
next = n1,n1=n2,n2= n3,n3 = n3->
next。这是循环向后走的赋值,顺序不能错,我们可以发现,什么时候停止-->
经过分析可以看到只要n2不为空,我们就还要向后走,因此循环的条件为n2!=NULL;
3、因题目要求返回头节点,因此我们只需要返回n1即可。return n1;
4、在上述循环中,我们移动n3是通过n3找n3的next,但是当我们到最后一次时,n3已经为空,如果我们再让n3 = n3->
next,会出现空指针异常,因此我们必须加上判断条件,并且在最后一次中,n3即使不再向后移动,原链表也会翻转,因为无序再向后走了。
2、方法二:struct ListNode* reverseList(struct ListNode* head)
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while(cur)
struct ListNode* next = cur->
next;
cur->
next = newhead;
newhead = cur;
cur = next;
return newhead;
2.1思路分析
头插法:
我们要达到逆置原链表,我们可以选择使用头插法。
我们创建一个新的头newhead,让newhead置为NULL,在创建一个cur指针指向原来的head,创建next指针用来保存cur的下一个指针。这个next节点也是必须创建的,原因是cur的next指向newhead后无法找到原链表中cur的next节点,因此我们必须让next保存这个节点。
其中:
1、我们让cur的next指向newhead,再让newhead指向cur,cur指向next,next指向next的下一个节点。顺序一定不能乱。循环停止的条件为,cur只要不为空,就可以一直头插,知道cur为空。
2、题目要求返回新的头结点,因此我们只需要返回newhead即可。
3、此方法我们无序考虑原链表是否为空,因为我们创建的newhead为NULL,如果原链表为空,即cur一开始就是空,不会进入到循环条件里面,直接return newhead,因此无需判断。
(本题完)
推荐阅读
- 信而泰一体化智能测试,助力客户降本增效
- “军备竞赛”时期的对比学习
- 40篇学完C语言——(第七篇)地址算术运算
- 就全懂了
- 学妹一反常态主动联系我,我要不要答应帮她()
- Cisco WLAN和WLC
- SC实现隐藏Windows服务维持权限
- #yyds干货盘点# 解决剑指offer(滑动窗口的最大值)
- 写着简单跑得又快的数据库语言 SPL