[LeetCode]92. 反转链表 II(Reverse Linked List II)

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路

指针。

代码

Python 3.6

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.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(-1)
dummy.next = head
cur = dummy
count = 0
while cur is not None:
if count == m - 1:
# 此时 cur 为不需要反转的最后一个节点
# 开始反转
last = cur # 不需要反转的最后一个节点
cur = cur.next
end = cur # 需要反转的第一个节点
count += 1
pre = None # 上一个节点
while cur is not None:
tmp = cur.next # 原下一个节点
cur.next = pre # 反转
pre, cur = cur, tmp
count += 1
if count > n:
# 结束反转
break
last.next = pre
end.next = cur
break
cur = cur.next
count += 1
return dummy.next

执行用时 : 52 ms
内存消耗 : 13.8 MB