1. 题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
2. 思路
题目要求一趟遍历。处理链表的题，一般会生成一个dummy Node，使得dummy Node指向链表的头结点。另外需要先定位到要反转链表的开始节点，并标记开始节点的前一节点，使得在翻转的过程中，始终能找到这一节点。
假设要反转的链表段如下：1—>2—>3
翻转过程如下：
pre—>1—>2—>3
pre—>2—>1—>3
pre—>3—>2—>1
2.1 代码：
class
Solution
:
def
reverseBetween
(
self
,
head
:
ListNode
,
m
:
int
,
n
:
int
)
-
>
ListNode
:
dummyNode
=
ListNode
(
-
1
)
# 先生成一个dummy节点
dummyNode
.
next
=
head
pre
=
dummyNode
for
i
in
range
(
m
-
1
)
:
pre
=
pre
.
next
# 定位到开始翻转链表的之前一个节点
cur
=
pre
.
next
for
i
in
range
(
m
,
n
)
:
# 开始反转
temp
=
cur
.
next
cur
.
next
=
temp
.
next
temp
.
next
=
pre
.
next
pre
.
next
=
temp
return
dummyNode
.
next
