92. 反转链表 II
https://leetcode.cn/problems/reverse-linked-list-ii/description/
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
解题思路
这题是 206. 反转链表 的衍生题目，可以理解为将链表根据left 和right 分成三段，将中间那一段进行反转
代码
type ListNode struct {
Val int
Next *ListNode
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
var preHead, r *ListNode
// preHead 指向头节点
preHead = &ListNode{
Val: 0,
Next: head,
}
// pre 用来记录遍历的上一个节点
pre := preHead
// tmp 用来记录需要反转的链表
tmp := preHead
for head != nil {
left--
right--
// 到达需要反转列表的头节点
if left == 0 {
// 切断列表，记录反转列表
pre.Next = nil
tmp = head
}
// 到达反转列表的尾部
if right == 0 {
// 切断列表，记录剩余部分
r = head.Next
head.Next = nil
}
pre = head
head = head.Next
}
// 反转链表
tmp = reverse(tmp)
res := preHead
// 拼接链表
for preHead.Next != nil {
preHead = preHead.Next
}
preHead.Next = tmp
for tmp.Next != nil {
tmp = tmp.Next
}
tmp.Next = r
return res.Next
}
func reverse(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var pre *ListNode
for head.Next != nil {
tmp := head.Next
head.Next = pre
pre = head
head = tmp
}
head.Next = pre
return head
}