这篇文章继续带大家手撕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. 代码优化，修改