92. 反转链表 II

题目

给你单链表的头指针 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

题解

翻转从 left 位置到 right 位置的链表，可以先遍历到 left-1 位置，然后开始翻转长度为 right-left+1 的链表。
翻转链表核心代码如下：

prev := dummy
curr := head
for i := 0; i < k; i++ {
    next := curr.Next
    second := next.Next
    next.Next = prev.Next
    curr.Next = second
    prev.Next = next // prev 重新指向 子链表 头节点
}

代码实现

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummy := &ListNode{Val: -1}
	dummy.Next = head
	p := dummy
	n := left - 1
	for n > 0 {
		p = p.Next
		n--
	}
	headNode, _ := reverseKList(p.Next, right-left)
	p.Next = headNode.Next
	return dummy.Next
}

func reverseKList(head *ListNode, k int) (*ListNode, *ListNode) {
	dummy := &ListNode{Val: -1}
	dummy.Next = head
	prev := dummy
	curr := head
	for i := 0; i < k; i++ {
		next := curr.Next
		second := next.Next
		next.Next = prev.Next
		curr.Next = second
		prev.Next = next // prev 重新指向 子链表 头节点
	}
	return prev, curr
}