Leedcode链表经典OJ

简介: Leedcode链表经典OJ

这篇文章继续带大家手撕Leedcode高频经典链表OJ,本期很精彩!




第二题:反转链表


OJ链接:206. 反转链表 - 力扣(LeetCode)


这道题在这里提供两种方法:

一 .  头插法

二.  三指针法

.  头插法如下

思路分析:

链表的反转,思路一:创建一个新链表,将原链表的各个节点依次头插到新链表,顺序刚好是反转后的链表。

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,符合题意。


心得总结:在拿到一道题时候,别着急直接敲代码,要按照上述程序一点一点分析,推敲。通过通过画图走下面程序

  1. 思路分析
  2. 细节分析
  3. 初步代码设计
  4. 极端分析
  5. 代码优化,修改
相关文章
|
29天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
24 7
|
4月前
【数据结构OJ题】环形链表
力扣题目——环形链表
36 3
【数据结构OJ题】环形链表
|
4月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
51 1
【数据结构OJ题】复制带随机指针的链表
|
4月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
29 1
【数据结构OJ题】环形链表II
|
4月前
【数据结构OJ题】相交链表
力扣题目——相交链表
32 1
【数据结构OJ题】相交链表
|
4月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
39 8
【数据结构OJ题】合并两个有序链表
|
4月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
32 1
【数据结构OJ题】链表中倒数第k个结点
|
4月前
【数据结构OJ题】链表分割
牛客题目——链表分割
29 0
【数据结构OJ题】链表分割
|
4月前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
36 0
【数据结构OJ题】链表的回文结构
|
4月前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
24 0
【数据结构OJ题】链表的中间结点