leetcode92 反转链表II

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

解析

这道题不太简单，分为两种方法，先说不好理解的那种方法，主要是官方题解中的第二种方法（一次遍历穿针引线头插法），注意这种反转和之前遇到过的都不一样，写的时候很容易出错（在画图的前提下，易错点都在下面代码里了）

代码如下：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummy := &ListNode{}
	dummy.Next = head
	pre := dummy
	for i := 0; i < left-1; i++ { // 注意这个left和right的值，自己画图的时候就能发现需要-1才合适
		pre = pre.Next // 此时移到了left所在的前一位
	}
	cur := pre.Next
	for i := 0; i < right-left; i++ { // 这个范围想不明白的话也是画图用测试用例来看
		next := cur.Next
		cur.Next = next.Next
		next.Next = pre.Next // 一定要注意这一步，不是指向cur，因为cur后面会走
		pre.Next = next
	}
	return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第二种方法是在之前反转链表的基础上改进，稍微好理解一点，直接调用之前的反转链表的方法（当然这个方法也可以改成不需要返回值）

func reverseBase(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil {
		return head
	}
	dummy := &ListNode{}
	dummy.Next = head
	pre := dummy
	for i := 0; i < left-1; i++ {
		pre = pre.Next // pre是left节点前面的一个节点
	}

	// 找到right节点
	rightNode := pre.Next
	for i := 0; i < right-left; i++ { // 画图画图，想不明白就画图
		rightNode = rightNode.Next
	}

	// 在此基础上切割出来一个子链表(先保留最后要链接的节点)
	leftNode := pre.Next
	rightAfter := rightNode.Next

	// 切断链表
	pre.Next = nil
	rightNode.Next = nil

	rightNode = reverseBase(leftNode) // 传入的其实是左结点，反转后返回的是右节点了

	// 接回去
	pre.Next = rightNode
	leftNode.Next = rightAfter

	return dummy.Next
}
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
38
39
40
41
42
43
44
45