算法：反转链表 II go实现
package main
import "fmt"
/*
92. 反转链表 II ----翻转部分链表
https://leetcode.cn/problems/reverse-linked-list-ii/
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
*/
/*
解题思路：
1.同第 206 题，反转链表的子区间 封装了这一层
2.外面需要做的处理是：1.缕清left前面，另起节点到right，切断链表，反转链表，接回原来的链表
*/
type NodeR struct {
data interface{} //数据域
next *NodeR //指针域
}
type ListNode struct {
length int //储存链表的长度
headNode *NodeR
}
func InitListR() *ListNode {
//即构造一个空的单链表L(包含头指针)
nodeR := new(NodeR)
L := new(ListNode)
L.headNode = nodeR
return L
}
func reverseLinkedList(head *NodeR) {
var pre *NodeR
cur := head
for cur != nil {
next := cur.next
cur.next = pre
pre = cur
cur = next
}
}
func (list *ListNode) reverseBetween(head *NodeR, left, right int) *NodeR {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
dummyNode := &NodeR{data: -1}
dummyNode.next = head
pre := dummyNode
// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 建议写在 for 循环里，语义清晰
for i := 0; i < left-1; i++ {
pre = pre.next
}
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
rightNode := pre
for i := 0; i < right-left+1; i++ {
rightNode = rightNode.next
}
// 第 3 步：切断出一个子链表（截取链表）
leftNode := pre.next
curr := rightNode.next
// 注意：切断链接
pre.next = nil
rightNode.next = nil
// 第 4 步：同第 206 题，反转链表的子区间
reverseLinkedList(leftNode)
// 第 5 步：接回到原来的链表中
pre.next = rightNode
leftNode.next = curr
return dummyNode.next
}
//从尾部插入
func (list *ListNode) AppendElem(v interface{}) {
node := &NodeR{data: v}
cur := list.headNode
for cur.next != nil {
cur = cur.next
}
cur.next = node
list.length++
return
}
func printlist(la *NodeR){
for {
if la.next == nil{
break
}
fmt.Print(la.next.data)
la = la.next
}
}
func main() {
La :=InitListR()
test := []int{1,2,3,4,5}
for i :=range test{
La.AppendElem(test[i])
}
node := La.reverseBetween(La.headNode,3,5)
printlist(node)
}