题目描述#

给你一个单链表的头节点 head，以及两个整数 left 和 right，其中 left <= right。

要求只反转链表中第 left 个位置到第 right 个位置之间的节点，其他部分保持原有顺序，最后返回新的链表头节点。

思路#

这份代码先创建了一个哑节点 dummy，并让它指向原链表头部。这样做的好处是，即使反转区间从第一个节点开始，也能统一按照“找到区间左边一个节点”的方式处理，不需要单独讨论头节点变化的问题。

接着用 pre 向后走 left-1 步，让它停在反转区间左边的那个节点上。此时 cur := pre.Next 就是反转区间的第一个节点。后面的操作不再整体翻转一段链表，而是重复做“头插”。

每一轮都先取出 cur 后面的节点 next，把它从原位置摘下来，再插到 pre 后面。这样一来，反转区间前部会不断变长，而 cur 始终留在这段已反转部分的尾部，继续和后面的节点相连。循环执行 right-left 次之后，区间内节点顺序就完全反过来了。

整个过程中只遍历了链表常数次，时间复杂度是 O(n)，额外只用了几个指针变量，空间复杂度是 O(1)。

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummy := &ListNode{Next: head}
	pre := dummy

	for i := 0; i < left-1; i++ {
		pre = pre.Next
	}
	// 此时pre为left左边的节点
	cur := pre.Next

	for i := 0; i < right-left; i++ {
		next := cur.Next
		cur.Next = next.Next
		next.Next = pre.Next
		pre.Next = next
	}

	return dummy.Next
}