题目：反转链表
要求：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL限制：
0 <= 节点个数 <= 5000
反转链表算是面试中比较常见的一个关于链表的题，整体上难度不大，但如果你能掌握多种的解法，往往可以让面试官眼前一亮
注意提醒一点，在面对链表的面试题时，建议多画一下图理解一下
解法 1：简单双指针
image
通过双指针，遍历 head 指针，通过中间变量，逐步指向新的 head 节点，完成链表反转
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
var newHead *ListNode
for head != nil {
node := head.Next
head.Next = newHead
newHead = head
head = node
}
return newHead
}
结果如下：
image
还有一种简化的写法，在同一步操作中，改变各个变量对应的值，可以省去中间变量，但这样阅读其实并不友好
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
var newHead *ListNode
for head != nil {
head, head.Next,newHead = head.Next, newHead, head
}
return newHead
}
image
解法 2：递归
整体思路是递归到最后一个节点，这个节点就是链表反转后的头节点，这里记作 ret，最终只需要返回这个 ret 指针即可，剩余的都是对中间数据进行指针反转。
具体要怎么分析呢？这样就要画个图了
image
image
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
ret := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return ret
}
递归去做其实不太容易理解，但也不失为一个巧妙的方法：
image
解法 3：双头指针
这个解法是参考 leetcode 大神的题解的，跟双指针的解法有点像，但更巧妙
image
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
cur := head
for head.Next != nil {
t := head.Next.Next
head.Next.Next = cur // 反转原指针方向
cur = head.Next // 将新头节点移到下一位
head.Next = t // 连接回断开的地方，继续重复上面操作
}
return cur
}
效果跟简单的双指针没差多少：
image
欢迎关注公众号：若鱼治水，文章会首发在公众号，也可备注加我备注进群进技术交流群～
