单链表经典OJ题：反转链表

---

目录

​编辑

题目：

图例：

 分析：

解法：

解法1：

解法2：

解法2本质：

代码演示：

n3要进行判断的原因：

方法二：

头插法：

---

题目：

给你单链表的头节点 head ，i请你反转链表，并返回反转后的链表。

图例：

 分析：

根据链表的特征，反转链表的本质便是改变节点内部的指针方向。

将原先指向下一个节点的指针进行修改，将其的指向修改成指向上一个节点。

解法：

根据分析我们可以得出两种解法：

解法1：

• 定义新链表，和移除元素的做法类似，但是使用的是头插方法。

解法2：

• 直接在原链表上改变指针的指向，这里需要运用三个指针。
• 第一个是最开始的设置为NULL的指针n1
• 第二个是开始从第一个节点开始遍历的n2
• 第三个是从第二个节点开始遍历的n3。
• n2是改变方向的，n3是保存下一个节点位置的，n1是被指方向的，三者同时开始遍历，只是遍历的位置不同。

解法2本质：

• 本质就是原先 节点 1的 1->next  指向的是2 变成了指向NULL。
•  原先节点2 的 2->next指向3 变成了指向节点1。
• 开始遍历的时候，首先将n2的指针指向变成n1，而后n1要变成n2，n2要变成n3，n3要变成n3->next

• 要注意n3在遍历过程中是最早指向NULL的所以要给n3设定一个判定条件，让n3及时停下。 
• 另外还要判定这个链表是否有节点，那么就是得判定第一个节点head是否存在。

代码演示：

• 因为n2最后要变成头节点，所以遍历的判定条件是n2是否为空 

n3要进行判断的原因：

当n3变成NULL的时候没必要继续进行移动，移动到最后一个节点。

方法二：

头插法：

设一个指针指向一个NULL，在设一个指针cur指向头节点，以及设置一个next指针表示cur->next，cur->next是保存节点的作用，cur表示头插，将cur->next改变方向指向newhead（新创造的一个指向NULL的指针），然后newhead移动，cur移动，next也因此改变。