题目描述

给你单链表的头指针 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. 反转链表。一种是先遍历链表，找到需要反转的链表的起点和终点，然后将起点和终点之间的链表反转。

另一种是直接在遍历链表的过程中找到需要反转的链表的起点，然后逐个反转节点，反转直到终点结束。两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummyNode := &ListNode{Val: 0, Next: head}
	prev := dummyNode
	current := dummyNode.Next
	position := 1

	// 移动到反转起点
	for position < left {
		prev = current
		current = current.Next
		position++
	}

	// 开始反转
	reverseStart := current
	for position < right {
		moveNode := current.Next
		preNext := prev.Next

		current.Next = moveNode.Next
        prev.Next = moveNode
		moveNode.Next = preNext

		position++
	}

	reverseStart.Next = current.Next

	return dummyNode.Next
}

这里主要需要注意几点：

  • position 变量用于记录当前节点的位置，方便判断是否到达反转的起点和终点。当第一个循环结束时，prev 指向反转起点的前一个节点，current 指向反转起点。
  • 因为 postion 默认为 1，之后每次 加 1，所以如果 left == right，第二个循环不会执行，直接返回 dummyNode.Next 即可。
  • 反转链表的过程是将当前节点（current）的下一个节点 (current.Next) 插入到反转起点前面（prev.Next），并将剩余的节点连接到反转起点（current）后面: 
    1
    2
    3
    current.Next = moveNode.Next
    prev.Next = moveNode
    moveNode.Next = preNext
    这里先把 moveNode 的下一个节点保存到 current.Next，然后将 moveNode 插入到 prev 后面，最后将 moveNode 的下一个节点指向 preNext，这样就完成了反转。