leetcode 92 反转链表

反转链表II

首先记录m-1的节点(front),然后依次倒置[m,n]之间的节点,期间还要注意m节点的收藏(tail),用来设置tail.next=back,然后记录n+1(back)节点,最后完成n+1,m-1连接。由于倒置是通过不停的选择next节点来完成,为了防止陷入死循环,本次节点(cur)与本次节点next节点(temp)的关系倒置要放到下一次循环中处理,这就需要我们引入pre来记录本次节点。
简而言之,介于[m,n]间的单次循环要完成两项任务:1. 设置temp 2. 完成cur.next = pre。
代码来源

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

class :
def reverseBetween(self, head, m, n):
cur = head
i = 0
back = tail = front = pre = None
while cur:
if m <= i <= n:
tmp = cur.next #task 1
if pre is None:
tail = cur #record m
cur.next = pre #task 2
pre = cur
cur = tmp
else:
if i == m-1:
front = cur #record m-1
elif i == n+1:
back = cur
cur = cur.next # !!move to the next!!
if front:
front.next = pre
res = head
else:
res = pre
tail.next = back
return res