反转链表是一个经典的问题，应用广泛，时间复杂度不高，实现起来也不难。本篇文章将介绍如何在golang中实现一个反转部分链表的算法。
反转链表
先来看看如何反转链表，我们可以用迭代或递归两种方式进行实现。
- 迭代方式
我们用三个指针pre、cur、next来迭代地进行反转操作，其中pre和next是为了保存cur的前驱和后继节点，便于反转后重新连接。代码如下：
func reverseList(head *ListNode) *ListNode {
var pre *ListNode = nil
cur := head
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}- 递归方式
递归方式虽然不如迭代方式好理解，但实际上是一个很好的练习递归思想的例子。递归操作需要注意的是，在递归到链表尾部之后，需要将尾节点赋值给head的Next节点，然后将尾节点作为新的head返回。代码如下：
立即学习“go语言免费学习笔记（深入）”；
func reverseListRecursive(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseListRecursive(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}反转部分链表
有了反转链表的基础，我们来看一下如何反转部分链表。题目描述如下：
主要更新介绍： 完美整合Discuz!论坛，实现一站式登陆、退出、注册； 同步所有会员资料； 新增购物车功能，商品购买更加方便、快捷； 新增部分快捷菜单，网站访问更加方便； 限制首页商品、店铺标题显示长度； 修正会员后台管理不能更改密码的错误； 完善商品显示页面所有功能链接； 修正后台标签管理部分错误； 修正前台学校列表不按后台顺序显示的错误； 修正搜索功能中学校名称过长导致显示紊乱的现象； 修正
给定一个链表和两个整数m和n，反转从位置m到n的链表。要求给出一种是算法实现。
通过观察题目，我们可以将他拆分成三个部分进行考虑：
- m之前: 不需要反转链表
- m到n之间: 需要反转链表
- n之后: 不需要反转链表
因此，我们需要用pre和tail变量来记录第一部分的尾节点和第二部分的头节点，然后将第二部分进行反转操作，反转后将第一部分的尾节点和第二部分的头节点连接即可。
代码如下：
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head == nil || m <= 0 || n < m {
return head
}
// 特判，如果m=1，则不需要第一部分
if m == 1 {
return reverseN(head, n)
}
// 遍历到m-1位置，记录pre和tail
var pre *ListNode = nil
cur := head
for i := 1; i < m; i++ {
pre = cur
cur = cur.Next
}
tail := cur // tail 记录第一部分的末尾是 cur
// 将第二部分进行反转操作
new_head := reverseN(cur, n - m + 1)
// 将第一部分与第二部分重新连接
tail.Next = new_head
if pre != nil {
pre.Next = tail
return head
} else {
return tail
}
}
// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
if head == nil || n <= 0 {
return head
}
if n == 1 {
return head
}
var pre *ListNode = nil
cur := head
for i := 1; i <= n && cur != nil; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
head.Next = cur
return pre
}总结
反转链表是链表类面试题的常客，掌握这一算法思想不仅可以解决反转链表问题，还能扩展到其他链表变换操作。在进行面试时，反转链表可能用作其他题目的子例，对于开拓思路非常重要。在golang中实现反转链表和反转部分链表算法，需要注意指针的使用、Nil的判断等问题，熟练掌握后代码实现起来非常简单。
