这篇文章继续带大家手撕Leedcode高频经典链表OJ,本期很精彩!
第二题:反转链表
这道题在这里提供两种方法:
一 . 头插法
二. 三指针法
一 . 头插法如下
思路分析:
链表的反转,思路一:创建一个新链表,将原链表的各个节点依次头插到新链表,顺序刚好是反转后的链表。
1. struct ListNode* reverseList(struct ListNode* head) 2. { 3. struct ListNode* newhead=NULL;//创建新链表 4. struct ListNode* cur=head;//备份head,用cur遍历链表 5. struct ListNode* next=NULL;//创建一个next指针,下面要用 6. while(cur)//原链表不为空就继续遍历 7. { 8. next=cur->next;//先存放下一个节点地址(下面要改,存下来以便下面迭代cur) 9. //头插cur到newhead 10. cur->next=newhead; 11. newhead=cur; 12. 13. //迭代cur,没有next就无法迭代,因为cur->next被改了 14. cur=next; 15. } 16. return newhead; 17. }
细节分析:
在这里,有一个指针next至关重要,如果没有提前保存cur->next,下面cur->next被改后,cur就无法迭代了。这里也体现了一种思维:重要数据被改前 提前备份。
极端分析:空链表反转,单个节点的链表反转。
如果原链表是空,循环就不会进去,直接返回newhead(NULL),符合题意。
如果链表是单个节点,next首先存NULL,然后头插cur,再cur改为NULL,出循环,返回newhead符合题意。
二 . 三指针法如下
思路分析:
创建两个指针n1 , n2,如下图
每次让n2指向n1,然后n2向后迭代,n1向后迭代
不断向后走,观察循环结束条件
据此观察,n2指针为NULL时,循环结束。链表被成功反转了,返回链表就行。
细节分析:
实现代码时,需先让n2->next指向n1,再迭代n1 和 n2,但是n2->next已经等于n1了,无法迭代n2了,所以我们借助上面同样的思想,重要数据被改前 提前备份,再创建一个指针next,每次循环提前备份n2->next。方便后面迭代。
代码设计:
1. 2. struct ListNode* reverseList(struct ListNode* head) 3. { 4. struct ListNode* n1=NULL;//起点n1是空 5. struct ListNode* n2=head;//n2是头节点 6. while(n2)//观察链表图,最后一次反转之后,n2为空。所以n2不为空,就继续迭代 7. { 8. struct ListNode* next=n2->next;//先备份n2->next,防止n2->next被改找不到原n2->next 9. 10. n2->next=n1;//每次让n2指向n1 11. 12. n1=n2;//n1向后迭代s 13. n2=next;//n2借助next向后迭代 14. } 15. return n1;//观察链表图,最后一次反转,n1是头节点,返回n1 16. }
极端分析:空链表反转,单个节点链表反转。
空链表反转:
当链表为空时:n2为空,无法进入循环,避免了next=n2->next出现空指针解引用问题。直接返回n1(NULL),符合题意。
单个节点链表反转:第一次循环,n2为单个节点的地址,next为NULL,n2指向n1,反转成功,n1 n2向后迭代,n2为空,n1是头节点地址。返回n1,符合题意。